[백준] 4375, 1, 모듈러 연산의 성질을 활용한 Overflow문제 해결

YUN·2026년 3월 4일

C++

목록 보기

60/86

문제 자체는 간단하다. 백준 1629번 (곱셈)과 상당히 유사한 문제이다.

각 자릿수가 1인수(1,11,111,1111,11111,...) 중에서 가장 작은 n의 배수의 자릿수를 찾아야한다.

문제 이해가 잘 안될때는 예제 입력이 어떻게 예제 출력으로 나오는지를 확인해보자

1%3!=0 -> 11%3!=0 -> 111%3=0 -----> 아하, 3의 배수 중 가장 작은 각 자릿수가 1인 수는 111이구나 -> 자릿수 3

이런 구조이다.

다들 처음엔 while문을 활용해서 cnt*10+1 하고 이를 n으로 나눠보며 나머지가 0인지 확인하는 로직을 생각했을 것이다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;

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

이를 기반으로 짠 코드이다.

이 코드는 큰 문제가 존재한다. long long a의 값을 cout 을 활용해서 찍어보면 long long 임에도 overflow 문제가 발생한다. (하긴, 배수 중에 모든 자릿수가 1인 확률 자체가 엄청 낮을것이다..그래서 계속 *10+1 연산이 수행될테고..)

이는 어떻게 해결할 수 있을까? 정답은 모듈러 연산 이다.

우리는 결국 a % n 이 0인지를 확인해야한다. 이렇게 모듈러 연산이 활용되는 연산은 모듈러 연산의 성질을 활용해서 Overflow 문제를 해결할 수 있다.

그럼, 모듈러 연산의 성질에 대해 알아보자

1. 모듈러 연산의 성질

위의 모듈러 연산의 성질을 이용해서 연산 과정에 나눗셈을 계속해서 넣어줘서 수의 크기를 제한 -> Overflow문제를 해결할 것이다.

2. 모듈러 연산을 문제에 적용

뭔가 복잡해보이는데, 나는 이렇게 이해했다.

3. 풀이

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n,ret;
    
    while(cin >> n) {
        int cnt = 1 % n;
        int ret = 1;
        while(cnt!=0) {
            cnt=(cnt*10+1)%n;
            ret++;
        }
        cout << ret << "\n";
    }
    return 0;
}