[BackJoon4375] 1

안녕하세요. 이번 포스팅에서는 BackJoon 4375번 문제인 1에 대한 해설을 진행해 보겠습니다.

 

문제는 다음과 같이 이루어져 있습니다.

 

 

우선 n이 2와 5로 나누어 떨어지지 않는다고 명시되어있습니다.

즉 주어지는 n은 10으로도 나누어 떨어지지 않습니다.

 

그러면 저희는 1부터 1 , 11, 111, 1111,... 11111111 등등 1로 이루어진 수를 계속 테스트하며 n과 나누어 볼 수 있습니다.

 

unsigned long long m = 1;
...
m = m * 10 + 1;

위와 같이 10을 곱하고 1을 더해주는 과정을 계속 진행해주면 1로만 이루어진 수를 작은 수부터 차례로 구해나갈 수 있습니다.

 

하지만 문제가 뭐냐면, 위 방식으로만 코드를 작성하게 되면 시간 초과가 나오게 됩니다. 그 이유는 오버플로우가 발생하기 때문입니다. 즉 수가 너무 커져서 아무리 큰 자료형을 사용하더라도 오버플로우가 나는 경우가 발생합니다.

 

즉 저희는 큰 수를 만들지 않으면서, 알고리즘을 계산하는 과정이 필요합니다.

 

여기서 modular라는 개념이 등장합니다.

 

만약 위의 코드를 

unsigned long long m = 1;
...
m = (m * 10)%n + 1;

 

이렇게 진행하면 어떻게 될까요?

 

저희가 원하는 결과를 얻는 것에 차이가 없습니다. 왜냐하면, 

3의 경우를 보면

 

11 / 3 = 몫은 3 나머지는 2입니다.

즉 11은 3 * 3 + 2입니다.

 

11 * 10 + 1 은 111입니다.

(3*3+2) *10 + 1로 나타낼 수 있고, %3을 적용한 상태로 넘어왔다고 하더라도

(3*3+2) *10 + 1 % 3 == 0? 과 (3+2) *10 + 1 % 3 == 0?은 결과적으로 차이가 없게 됩니다. 저희는 몫을 구하는 것이 아니라, 나누어 떨어지는지 아닌지만 확인하는 것이기 때문에 필요 없는 몫을 지우고 다음 단계로 넘어가는 것입니다.

 

이렇게 되면 주어진 자료형에서 오버플로우를 발생하지 않으면서 모든 수에 대해 검사를 진행할 수 있습니다.

 

 

<소스코드>

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

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

    int n;
    while(cin >> n) {
        int res=1;
        unsigned long long m = 1;
        while(true) {
            if (m % n == 0) break;
            else m = (m*10)%n + 1, res++;   
        }
        cout << res << endl;
    }
    return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.