[백준알고리즘] 4375번: 1 -C++ (테스트케이스의 개수가 주어지지 않은 경우)

[백준알고리즘] 4375번: 1 -C++ (테스트케이스의 개수가 주어지지 않은 경우)

4375번: 1 (acmicpc.net)

4375번: 1

정수론 문제를 보다가 재밌어 보여서 풀어봤다. 처음에 문제가 뭔 소리인지 몰랐다가 문제를 이해하고 나서는 쉽게 풀 수 있었다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

문제에서 요구하는 것은 정말 1로 이루어진 수(1, 11, 111,...) 중에서 N의 배수인 값의 자릿수를 구하는 것이다. 따라서, 정말 간단하게 뒤에 1을 붙이면서 N으로 나누어 떨어지는지 확인하면 된다.

 

그런데, 1로만 이루어진 수가 N의 배수를 만족하려면 웬만해서는 엄청 자릿수가 커질 것이라는 느낌이 온다. 그래서 모듈로 연산을 이용하기로 한다. 모듈로 연산의 특징은 아래와 같다.

• \((A + B) \% N = (A\%N + B\%N) \% N\)
• \((A - B) \% N = (A\%N - B\%N) \% N\)
• \((A * B) \% N = (A\%N * B\%N) \% N\)

 

모듈로 연산을 이용하면, 큰 수에 대한 나머지 연산을 작은 수를 이용해서 할 수 있다는 장점이 있다. 이 문제에도 모듈로 연산을 적용해 1로만 이루어진 수를 실제로 크게 적용하지 않아도 된다. 재귀적인 특성으로 모듈로 연산을 사용하면 된다.

• \(1 \% N\)
• \(11 \% N = (1 * 10 + 1) \% N\)
• \(111 \% N = (11 * 10 + 1) \% N\)

이렇게, 이전 연산 결과를 사용해 나가면 실제로 큰 수를 다루지 않고도 나머지 연산을 쉽게 할 수 있다.

 

이 문제에서는 특이한 점이 하나 있다. 바로 테스트케이스의 개수가 정해지지 않았다. 이럴 때에는 EOF까지 입력을 받아야 한다. C++을 이용할 때는 아래와 같이 scanf()의 결과가 EOF(-1)인지 확인하면 된다. scanf()의 man page를 보면 return value에 대한 내용은 아래와 같다.

RETURN VALUE

On success, these functions return the number of input items successfully matched and assigned; this can be fewer than provided for, or even zero, in the event of an early matching failure.

The value EOF is returned if the end of input is reached before either the first successful conversion or a matching failure occurs. EOF is also returned if a read error occurs, in which case the error indicator for the stream (see ferror(3)) is set, and errno is set to indicate the error.

 

아래는 문제를 통과한 코드다.

#include <cstdio>

int main(void) {
	/* 입력 */
	int N;
	while ( EOF != scanf("%d", &N) ) {

		/* 계산 */
		int iAnswer = 1; // 자리수
		int iModulo = 1 % N;
		while ( 0 != iModulo ) {
			iModulo = ((iModulo * (10 % N)) % N + (1 % N)) % N;

			// 자리수 증가
			iAnswer++;
		}

		/* 출력 */
		printf("%d\n", iAnswer);
	}

	return 0;
}