[C++] 백준 4375번 - 1 (시간초과, Modular 연산 활용)

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

4375번: 1

 

 

문제

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

입력

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

출력

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

 

 

---

접근 방법

숫자를 1, 11, 111, 1111,,,,로 키워가면서 N으로 나눠지는지 따지는 문제이다.

그러나 계속 숫자를 한 자리씩 키워나간다면 long long int 의 범위(-9,223,372,036,854,775,808~9,223,372,036,854,775,807)도 넘어가게 되고 시간초과가 뜬다. 그래서 modular 연산의 활용이 필요하다.

 

x mod N = (x mod N) mod N 임을 이용해보자.

 

예를 들어, 111이 N으로 나눠지지 않아서 1111로 넘어갈 때, 1111을 바로 다음 반복문으로 넘기는 것이 아니라 mod N 연산을 해주고 넘기는 것이다. 그러면 숫자가 계속 커지는 것을 방지할 수 있다.

 

숫자가 매우 커질 때 modular 연산을 이용해서 줄일 수 있다는 것을 기억하자!

//
//  수학_BOJ4375_1.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/28.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    
    int N;
    int k = 0;
    while(cin >> N){
        int ans = 1;
        k = 1;
        
        while(1){
            if(ans % N == 0){
                break;
            }
            else{
                k++;
                ans = ans*10 + 1;
                ans %= N;				//mod 연산을 해 준 결과를 다음 반복문으로 넘긴다.
            }
        }
        
        cout << k << "\n";
    }

    return 0;
}

 

 

참고)

 while(cin >> input) 은 입력이 종료될 때 까지 받는다. 

같은 의미로는 아래와 같다.

while(1){

  if(cin.eof() == true) {break;}

}