[1단계] 기본 문법 + 자료구조 기초

[cyeji]

알고리즘

• 1
• 약수
• 약수의합
• 소수찾기

[cyeji]

• 1

생각한 방식

1을 계속 증가시켜 대상 값이랑 나누어 떨어지면 해당 값의 자리수를 계산하는 방식으로 하였는데 이러다보니 Long의 제한 값 보다 길어지는 경우가 발생하는 듯.. NumberFormatException으로 실패함.

문제풀이 아이디어

• 모든 자리수가 1인 수를 1, 11, 111, ... 순으로 만들지 않고 나머지(modulo)만 계산한다.
• 숫자가 커져도 나머지만 보면 되므로 오버플로우 걱정 없음: 새 나머지 = (이전나머지 * 10 + 1) % n.
• n이 2나 5로 나누어지지 않으면 반드시 어떤 단계에서 나머지가 0이 되어 해당 자릿수의 수가 n의 배수가 된다. 시간 복잡도 O(n).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * https://www.acmicpc.net/problem/4375
 */

public class Main {

    public static void main(String[] args)  {
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
            String input = "";
            while ((input = br.readLine()) != null) {
                Long target = Long.parseLong(input);
                calculate(target);
            }

        }catch (IOException e) {
            e.printStackTrace();
        }

    }

    /**
     * 1의 배수가 나올때까지 구하기
     * @param target
     */
    private static void calculate(Long target) {
        int count = 2;
        while (true) {
            Long num = Long.parseLong("1".repeat(count));
            if (isOneMultiple(num, target)) {
                System.out.println(count);
                break;
            } else {
                count++;
            }
        }
    }

    private static boolean isOneMultiple(Long number, Long target){
        return number % target == 0;
    }

}