백준 4375 : 1(C++)

문제

풀이

입력받은 숫자가 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;
}