백준 4375번: 1(JAVA)

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

4375번: 1

 

[코드]

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true) {
			String s = br.readLine();
			if(s == null)
				break;
			else {
				int n = Integer.parseInt(s);
				int num = 0;
				
				for(int i = 0; ; i++) {
					num = (num * 10 + 1) % n;
					
					if(num == 0) {
						System.out.println(i+1);
						break;
					}
				}
			}
		}
	}
}

 

[풀이]

처음 접근법은 num = 1, 11, 111, ... 증가 시켜가면서 가장 작은 n의 배수를 찾아 나서는 것이었다.

하지만 이렇게 하면 num의 크기가 정수 범위를 벗어나게 되는 경우가 발생한다. (ex: n = 9901)

따라서 num = 10*a + 1 일 떄,

num%n = (10*a + 1) % n 이라는 특성을 이용해 정수 범위 내에서 배수를 구하는 방법을 사용해볼 수 있다.

 

예를 하나 들어보자.

n이 7일때,

1 % 7 = 1

11 % 7 = (1*10 + 1) % 7 = (1%7*10 + 1) % 7

111 % 7 = (11*10 + 1) % 7 = (11%7*10 + 1) % 7

1111 % 7 = (111*10 + 1) % 7 = (111%7*10 + 1) % 7

...

즉, num % 7 = ( (num-1)%7 * 10 + 1) % 7 임을 알 수 있다.

 

 

.