입력받은 숫자가 1, 11, 111,,, 111----111 중 나누어떨어지는 수를 찾으면 됩니다.
처음에는 밑에 있는 코드처럼 풀었습니다.#include <iostream> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; while(cin >> n) { long long num = 1; int count = 1; while(1) { if(num % n == 0) { cout << count << "\n"; break; } num = num * 10 + 1; count++; } } return 0; }
결과는 시간초과였습니다.
코드 하나를 추가해서 해결했습니다.
예를 들어서 3을 입력받으면 답은 111입니다.
11 x 10 + 1 = (3x3+2)x10 + 1 로 나타낼 수 있습니다.
어차피 3으로 나눌 것이기 때문에 3x3부분을 계산에서 생략해주면 시간을 줄일 수 있습니다.
따라서, num %= n; 코드를 추가하면 됩니다.
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n;
while(cin >> n) {
long long num = 1;
int count = 1;
while(1) {
if(num % n == 0) {
cout << count << "\n";
break;
}
num %= n;
num = num * 10 + 1;
count++;
}
}
return 0;
}