[백준 4375 / C++] 1

이 문제는 다음과 같이 풀면 된다. 

1

11

111

1111

............

..............

................

이런식으로 이어질텐데 저 값 순서대로 입력받은 값으로 나누었을 때 나누어지면 그 길이를 출력해주면 된다. 

하지만, 여기서 주의할 점은 int형의 범위를 넘어설 수 있으니 long long 의 타입으로 설정을 해주어도 문제를 해결 할 수 없다. 즉, long long 64비트에 해당하는 정수값을 넘어설 수 있다는 얘기다. 

그렇기 때문에 좀 더 깔끔한 방법이 필요한데 나머지를 초기화 시켜주는 것이다. 

 

예를 들면, n=3 일 때 

 

(첫번째 방법 - 틀린 것) 

11에서 3을 나누었을 때 나누어지지 않으니까 1을 더 추가해서 111로 만들어준 후 다시 3으로 나눈 나머지를 확인한다. 

 

(두번째 방법)

11에서 3을 나누었을 때 나누어지지 않으니까 나머지로 초기화 시켜주면 2가 되고 뒤에 1을 추가하면 21로 만들어준 후 다시 3으로 나눈 나머지를 확인한다. 

 

즉, 111을 3으로 나누든 21을 3으로 나누든 나머지는 0이라는 것은 같다.

그렇기 때문에 나타낼 수 있는  n의 배수는 n으로 나누어 떨어진다는 나머지의 성질을 이용해야 한다.

 

 

#include <iostream>
#include <string>
using namespace std;
int main() {
	int n;
	while (cin>>n) {
		int check = 0;
		int cnt = 1; 
		while (1) {
			cout << check<<"\n"; 
			check = check * 10 + 1;
			check %= n;
			if (check== 0) {
				printf("%d\n", cnt); 
				break;
			}
			cnt++;
		}
	}
}

 

4375번: 1