백준 4375번 1

문제 링크 : https://www.acmicpc.net/problem/4375

4375번: 1

 

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

 

입력

입력을 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

 

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

 

풀이

이 문제는 문제 조건에 2와 5로 나누어 떨어지지 않는 정수 n의 배수인 1로만 이루어진 수를 찾는 문제이기 때문에 반드시 정답이 존재할 수밖에 없다.

우선, 비둘기집 원리에 의해 1, 11, 111, 1111 등 1로만 이루어 진 수가 n+1개가 있을 때, 이들 중 n으로 나눈 나머지가 같은 두 수가 존재한다. 따라서 두 수의 차(111111.. 00)도 n의 배수가 되어야 하고 n은 2와 5의 배수가 아니므로,

역서 0을 모두 빼주면, 1로만 이루어진 수가 된다.

 

추가로, 1로만 이루어진 수들을 실제로 직접 더해가며 구하면, long long 범위를 초과할 수 있기 때문에, 이 문제는 n의 배수는 n으로 나누어 떨어진다는 나머지의 성질을 이용해야 한다.

따라서, 각 자릿수를 n으로 나누어가며 자릿수를 점점 추가((k * 10 + 1) % n)하면서 나머지가 0일 때 몇 번 계산했는지 구하면 된다.

코드를 보면 이해가 훨씬 빠를 것이다.

 

소스 코드

#include <iostream>
using namespace std;
int main() {
    int n;
    while (cin >> n) {
        int num = 0;
        for (int i = 1;i<=n; i++) {
            num = num * 10 + 1;
            num %= n;
            if (num == 0) {
                printf("%d\n", i);;
                break;
            }
        }
    }
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~