[구현 / BOJ 4375 / C++] 1

https://www.acmicpc.net/problem/4375

4375번: 1

문제는 간단하다. 딱 1로만 이루어진 수 ( 1, 11, 111, 1111 ......) 를 구해서 자리수만 구하면 되는 문제이다.

 

로직을 정리하자면, 

 

1. for문을 통해 1, 11, 111, 1111, ... 과 같이 1로만 된 수를 구한다.

2. 만약, 주어진 n으로 나눠떨어지는 1로만 된 수가 나오면 break 한다.

3. 그 숫자의 자리수를 구해 출력한다.

 

이다. 그러나 이걸 직접 실행해보면 오버플로우의 지옥을 맛보게 될 것이다.

n=9999 일때를 생각해보자,,, 얼마나 많은 1이여야할까..

 

그래서 이렇게 무식하게 하는 방법 대신 뭔가 새로운 방법을 알아야한다. 

바로 수학 공식을 이용해야한다. (모듈러 공식)

 

(A +B) % C = { (A%C) + (B%C) } %C

 

이를 이용하면 {1 % C + 10 % C + 100 % C} % C = 111 % C  로 이해할 수 있다.

즉 위의 로직을 조금 응용해서,

 

1. cnt= 1 로 하고, cnt = 10 *  cnt + 1, cnt %= n,  를 한다. 동시에 ret 를 늘려준다.

2. 만약 cnt%n == 0 이 되면 반복을 종료하고 ret를 출력한다.

 

while(cin>>n) 은 입력이 종료될때까지 입력을 받는 방식이다.

 

모듈러 연산은 처음에는 어렵지만 익숙해지면 좀 나아질 것이다. 

#include <bits/stdc++.h>

using namespace std;

int n;

int main(){
    while(cin>>n){
        int cnt=1, ret=1;
        while(true){
            if(cnt%n==0) {
                cout << ret <<'\n';
                break;
            }else{
                cnt = cnt*10 + 1;
                cnt%=n;
                ret++;
            }
        }
    }
    
    return 0;
}