백준 4375 : 1

www.acmicpc.net/problem/4375

4375번: 1

1 ~ 10000 사이의 수 n이 주어졌을 때 n의 배수 중 1로만 이루어진 수(ex- 1, 11, 111, 1111, ...)의 자리수를 구하는 문제이다. 

 

처음에는 단순히 확인하고자 하는 수의 길이를 늘려가면서 ( 1, 11, 111, 1111, 11111 ... ) n으로 나누어 떨어지는지를 체크하였는데 이 경우 나누어 떨어지는 수를 찾기 전에 오버플로우가 나게 된다. 그래서 직접 손으로 나눗셈을 하는 것과 같은 방식으로 코드를 구현하였다. 예를 들어 n이 3인 경우를 살펴보자. 확인자고자 하는 수를 m이라고 하면,

m = 1인 경우를 먼저 확인한다. 1 % 3 = 1이고 이 값을 다시 m에 저장한다.

다음 수(11)를 확인하기 위하여 (m = 10*m + 1)를 해주고 다시 모듈러 연산을 취해준다. 이 때, 11 % 3 = 2이고 이 값을 다시 m에 저장한다.

다음 수(111)를 확인하기 위하여 다시 (m = 10*m + 1)를 해준다. 이때 m은 21이 되는데 이 값은 우리가 손으로 나눗셈을 할 때 처럼, 다음과 그림과 같은 연산을 통하여 얻은 값이다. 이제 다시 모듈러 연산을 취해주면 나머지가 0이 되므로 111은 3으로 나누어 떨어짐을 확인할 수 있다. 이와 같은 방법을 사용하여 오버플로우가 나지 않고 문제를 해결할 수 있다.

 

 

 

 

#include <iostream>

using namespace std;

int main() {
	int n, digit = 1;
	long long m = 1;
	while (cin >> n) {
		while (m % n != 0) {
			m %= n;
			m = 10 * m + 1;
			digit++;
		}
		cout << digit << '\n';
		m = 1, digit = 1;
	}

	return 0;
}

메모리: 2016 KB

시간: 0 ms