백준 4375번 - 1

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

4375번: 1

 

풀이 과정

 입력 받은 n을 111....1까지 만드는 것이 아니라 1부터 시작해서 11, 111, 1111...을 n으로 나눠 0이되는 자릿수를 찾아야한다. 어떻게 보면 역발상이 필요하다고 할 수도 있다. 

 

느낀 점

 숫자와 관련된 문제가 나오면 어떤 복잡한 규칙을 찾기에만 매진하게 된다. 일단은 단순하게 구현할 수 있는 방법은 없는지 먼저 생각해보자.

 

#include<bits/stdc++.h>
using namespace std;

int n, a, cnt;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	while (cin >> n) {
		a = 0; cnt = 0;
		do {
			cnt++;
			a = (a * 10) + 1;
			a %= n;
		} while (a != 0);
		cout << cnt << "\n";
	}
	
	return 0;
}