[BOJ/C++] 4375::1 (브루트포스, 정수론)

1

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	24672	8145	6066	32.225%

 

문제

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

 

입력

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

 

출력

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

 

예제 입력 1 복사

3
7
9901

예제 출력 1 복사

3
6
12

 

---

후기

다국어 문제이기에 이해하는데 시간이 조금 걸렸지만, 생각보다 문제는 쉬웠다.

 

문제가 원하는 것은, 입력된 숫자로 1로만 이루어진 수가 나올도록 하는 것이다. 물론 5나 2같은 짝수가 주어지면 안되기에 이 부분은 문제가 알아서 전달해준다.

 

이번 문제는 해결 방법을 알아내는 것은 금방했지만, 연산 숫자가 너무 커지거는 경우 출력에 문제가 발생한다.

 

1. 연산 크기가 늘어날 수록 출력에 문제가 생긴다.

   • while (multiple % num != 0) {
         multiple = multiple * 10 + 1;	// 10배씩 증가하는 숫자 감당 불가능
         multiple %= num;			// 애초에 0이 남을때까지 나눌 것이기에 미리 계속 나누기 연산을 한다.
         count++;
     }

2. 반복문을 통해 입력 값을 받을 때, 줄바꿈 문자가 먼저오고 eof가 오는 경우 예기치 못하게 한 번 더 반복한다.

   • int num;
     while (!cin.eof()) {	// 줄바꿈 문자에 1회 더 회전, count를 초기화함
         int count = 1;
         int multiple = 1;
         cin >> num;
     
         while (multiple % num != 0) {
             multiple = multiple * 10 + 1;
             multiple %= num;
             count++;
         }
     
         cout << count << endl;
     }

 

위 문제점을 해결한 코드는 다음과 같다.

 

 

#include <iostream>

using namespace std;


int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int num;
    while (cin >> num) {
        if (cin.eof()) break;
        
        int count = 1;
        int multiple = 1;

        while (multiple % num != 0) {
            multiple = multiple * 10 + 1;
            multiple %= num;
            count++;
        }
        
        cout << count << endl;
    }
    
    return 0;
}