본인 풀이

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

ll square(ll mult){
    if(mult == 0){
        return 1;
    }
    if(mult == 1){
        return 10;
    }
    // 홀수제곱
    if(mult % 2){
        return 10 * square(mult / 2) * square(mult / 2);
    }else{
        return square(mult / 2) * square(mult / 2);
    }
}

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

    ll count = 0;
    ll num;

    cin >> num;

    // 시간초과
    while (1){
        ll ret = 0;
        for (ll i = 0; i <= count; i++){
            ret += square(i); // square(0) + square(1) + square(2) => 1 + 10 + 100
        }
        count++;
        if (ret % num == 0)
        {
            break;
        }

    }
    cout << count << "\n";

    return 0;
}

1. 시간초과 났음
2. 10의 제곱을 출력해주는 함수를 생성했음 - nlogn 시간 (제곱함수 재귀호출에 logn, count변수 n번까지하여 111...11 수를 만들어야 해서 n)
3. 애초에 시간복잡도 문제가 아닌, long long 타입 오버플로우 문제였음.

모범 답안

로직은 어느정도 맞다고 할수 있으나, 최대범위를 벗어난 데이터 내에서 while 무한루프가 발생하여 시간초과가 발생하는 것이었다. 정수론 모듈로 연산을 적용해야 한다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;

int main()
{
    while(scanf("%d", &n) != EOF){
        ll cnt = 1, ret = 1;
        while(true){
            if(cnt % n == 0){
                printf("%lld\n", ret);
                break;
            }else{
                cnt = ((cnt * 10)) % n + (1) % n;
                // 엄밀히 따지면, (cnt % n * 10 % n) + 1임
                ret++;
            }
        }
    }

    return 0;
}

입력값이 무한대로 주어지기 때문에 while(scanf("%d", &n) != EOF)로 시작해야 한다. 나머지는 정수론의 모듈로 연산에 입각하여 로직을 구성한다.