백준 4375 1(C++)

* 해당 문제 풀이는 '큰돌'님의 문제풀이에서 제가 이해한 부분을 재작성한것입니다

백준 4375 1 입니다

 

문제 풀이

이문제를 처음 봤었을때 살짝 이해가 안되었습니다

우선 n은 2 와 5 로 나누어 떨어지지 않는 정수 즉 (n % 2) && (n % 5) 라는 부분은 쉽게 이해가 되었습니다

그러나 그 다음부분인 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오 에서 이해가 잘안되었습니다

1로만 이루어진... 처음에는 소수인가?.. 라는 생각이 들었지만 풀이를 확인해보니 정말로 1 로만 이루어진 숫자였습니다.. 즉

1 - 11 - 111 - 111 ... 와 같이 모든 자리수가 1로만 이루어진 숫자입니다

 

이러한 숫자가 n의 배수일때 이숫자의 자리수를 출력하면 되는 문제입니다

 

그러면 첫번째 1로만 이루어진 숫자를 어떻게 만들까요?

우선 시작값은 1로 시작을 합니다 그리고 (시작값 * 10) + 1 을 해주면 됩니다

즉 (1*10) + 1 = 11 이나오게됩니다

이부분을 계속 반복을 시켜주면 1로만 이루어진 숫자를 만들수 있습니다

(1*10) + 1 = 11 -> (11 * 10) + 1 = 111 -> (111 * 10) + 1 = 111 ...

 

그 이후 이숫자를 n으로 나누었을때 0이 나오면다면 해당 숫자에 자리수를 출력해주면 됩니다

 

그러나 여기서 문제 한가지가 나오게됩니다

예제와 같이 9901 이라는 숫자를 입력했을때 1의 자리수는 12가 나오게됩니다

하지만 int 자료형의 자리수는 10자리밖에 안되기에 1로만 이루어진 숫자를 만들다보면 오버플로우가 발생을 합니다

 

이러한 문제를 해결 하긴 위해서는 mod 연산을 특징을 적용해야합니다

(a+b) % n 의 결과는 ((a % n) + (b % n)) % n 과 같습니다 즉

계산이 완료된 이후에 mod연산을 한 결과와 계산하는 중간에 mod연산을 한 결과는 같다 라는 특징있습니다

 

이러한 특징을 적용해서 1로 이루어진 숫자가 만들어지고 바로 n의 mod연산을 해줍으로써 자리수를 줄일수있습니다

 

문제풀이순서

1. 정수 n, 1로만 이루어진 수, 자리수를 카운팅할 변수를 선언합니다

2. 해당 문제는 종료 시점이 없기에 while 과 scanf를 써서 계속 n을 입력 받습니다

3. n이 입력될때 마다 1로만 이루어진 수 와 자리수를 1로 초기화 합니다

4. 이후 1로만 이루어진 수가 n의 배수일때 까지 반복문을 진행합니다

5. 이때 만약 1롬나 이루어진 수가 n의 배수일경우 자리술르 출력하고 반복문을 종료합니다

6. 아닐경우 1로만 이루어지는 숫자를 만들어줍니다

7. 오버플로우 방지를 위해 숫자가 만들어질때마다 n으로 mod연산을 진행합니다

8. 계산 이후 자리수를 구해줍니다

 

작성 코드

#include<bits/stdc++.h>
using namespace std;


//정수 n, 1로만 이루어진 수(cnt), 자리수 결과(ret)
int n,cnt,ret;
int main(){
    
    while(scanf("%d",&n) != EOF){
        //n 이 입력될때마다 수 와 자리수결과를 초기화
        cnt = 1;
        ret = 1;

        //1로만 이루어진 수가 n의 배수일때 까지 반복한다
        while(true){

            //만약 1로만 이루어진 수가 n의 배수일경우 자리수를 출력하고 반복문을 종료한다
            if(cnt % n == 0){
                cout << ret << "\n";
                break;
            }else{
                //n의 배수가 아닐경우 1로만 이루어지기에 수 * 10 + 1를 해준다
                cnt = (cnt * 10) + 1;

                //자리수가 높아질경우 오버플로우가 발생할수있기때문에 계산마다 mod연산을 진행한다
                cnt = cnt % n;

                //자리수를 구한다
                ret++;
            }
        }
    }
    return 0;
}