🥈[백준, 4375] 1 (Java)

 

문제 링크

4375번: 1

 

난이도

 

문제

 

풀이 과정

처음에 1, 11, 111, 1111을 만들면서 n으로 나누어 떨어졌을 때를 찾았더니 시간 초과가 났다.

사실 생각해 보면 당연한 거다. 자릿수에 대한 제한이 없으니 1로만 이루어진 11자리가 되는 순간 이미 int형(약 21억)을 초과하게 된다.

 

나머지 연산의 법칙

 

도저히 모르겠어서 풀이를 참고하여 "나머지 연산의 법칙"을 알게 되었다.

 왜 이렇게 되는지 궁금해서 증명을 해봤다.

그 과정이 궁금하다면 이를 자세히 설명한 블로그를 참고 바란다.

모듈러 연산의 성질과 증명

 

예시를 들어서 풀이

 

다른 사람의 풀이를 봐도 이해가 안돼서 진짜 거의 4시간 동안 이해하기 위해 노력했다.

 

먼저 1, 11, 111의 관계성을 파악한다.

처음에는 1, 1+10, 1+10+100.. 이런 식으로 생각했는데 물론 이 규칙도 맞지만 매번 다른 수가 더해지기 때문에 풀이하기 힘들다.

 

1, 1*10+1, (1*10+1)*10+1... 이전의 숫자에 10을 곱하고 1을 더하면 그다음 수가 된다. 항상 같은 규칙을 가지기 때문에 풀이하기 좋다.

 

그 다음 예시를 살펴보며 범위가 넘지 않도록 수를 줄일 수 있는 방법을 찾는다.

위의 사진을 살펴보면 111 % n의 값이 (11% n)*10+1의 값과 같은 것을 볼 수 있다. 

7로 나눠진 몫은 항상 7로 나눴을 때 0이 되므로 해당 수식이 나온다. (이걸 이해 못 해서 장장 4시간을..)

 

이를 토대로 식을 세워서 코드를 작성했다.

 

코드

 

public class BOJ_4375 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        while (true) {
            try {
                int n = Integer.parseInt(br.readLine());

                int cnt = 1;
                int prev = 1;

                while ((prev = prev % n) != 0) {
                    cnt++;
                    prev = prev * 10 + 1;
                }
                sb.append(cnt).append("\n");
            } catch (Exception e) {
                break;
            }
        }

        System.out.println(sb);
    }
}