백준 4375 1(JAVA)

문제 설명

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

 

풀이과정

 number를 계산할 때 단순하게 number = number * 10 + 1 을 한다면 시간초과가 나게 된다. 따라서 모듈러 연산을 수행해야 한다.
 (a * b) % c = (a % c * b % c) % c 와 같다는 점을 이용한다.
 111 % 3 = (11 * 10 + 1) % 3 = (11 % 3 * 10 + 1) % 3 = 21 % 3 = 0

 

정답코드

import java.io.*;
import java.util.*;

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 input = "";
        while ((input = br.readLine()) != null) {
            int num = Integer.parseInt(input);

            int number = 1;
            int cnt = 1;
            while (number % num != 0) {
                number = (number * 10 + 1) % num;
                cnt++;
            }

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

        bw.flush();
    }
}