4375번: 1

문제

2와 5로 나누어 떨어지지 않는 정수 n이 주어졌을 때, 1로만 이루어진 n의 배수 중 가장 작은 수의 자릿수를 구하는 문제입니다.

• 입력: 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 정수 n (1 ≤ n ≤ 10000)이 주어집니다.
• 출력: 각 테스트 케이스마다 1로만 이루어진 n의 배수 중 가장 작은 수의 자릿수를 출력합니다.

풀이

1로만 이루어진 수(1, 11, 111, 1111...)를 만들며 n으로 나누어 떨어지는지 검사하는 문제입니다.

1. EOF(End of File) 처리: 테스트 케이스의 개수가 명시되어 있지 않으므로, BufferedReader.readLine()이 null을 반환할 때까지 반복해서 입력을 받아야 합니다.
2. 모듈러(나머지) 연산 최적화 (오버플로우 방지): 1로만 이루어진 수를 tmp = tmp * 10 + 1 방식으로 계속 늘려가면, n의 값에 따라 자릿수가 수천 자리가 될 수 있어 long 타입의 범위(약 19자리)조차 금방 초과하게 됩니다. 따라서 모듈러 연산의 분배 법칙을 활용하여, 수를 키울 때마다 n으로 나눈 나머지만 tmp에 저장하는 방식으로 변경해야 오버플로우 없이 문제를 해결할 수 있습니다. tmp = (tmp * 10 + 1) % n;

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       String s;
       // 1. 입력의 끝(EOF)까지 반복
       while ((s = br.readLine()) != null) {
          int n = Integer.parseInt(s);

          int tmp = 1;
          int ans = 1;
          
          // 2. n으로 나누어 떨어질 때까지 반복
          while (tmp % n != 0) {
             // 3. 자릿수를 늘려가며 n으로 나눈 나머지만 유지 (오버플로우 방지)
             tmp = (tmp * 10 + 1) % n;
             ans++;
          }

          bw.write(ans + "\n");
       }

       bw.flush();
       bw.close();
       br.close();
    }
}

알고리즘 분류

수학 (Math), 브루트포스 알고리즘 (Brute Force)