C++ 백준 4375번 [1] 이라는 나머지 연산 속성 활용 문제

4375번: 1

 

나머지 연산의 성질은 알고리즘에서 종종 큰 수를 표현하기 위한 방법으로 사용되니 확실히 알아 둘 필요가 있다. 일단 이 문제에서 쓰이는 것만 확인해봤다.

 

첫 번째 접근

이 문제는 1, 11, 111... 과 같이 1로 이루어진 수를 주어진 n으로 나누어 0으로 떨어질 때 1로 이루어진 수의 자리수 개수를 출력하는 문제다.

 

그럼 1, 11, 111... 을 순서대로 n으로 나누어보면서 반복하면 된다.

1%n
11%n
111%n
1111%n
...

위와 같은 플로우를 반복문으로 정리한다.

int div = 0, cnt = 1;
while (true)
{
    div = div * 10 + 1;
    if( div%n == 0)
        break;
    cnt++;
}

위 식을 풀면 아래와 같이 작동한다. 첫번째 결과가 다음번째 식에 사용되고있다.

1 = 0 * 10 + 1;
11 = 1 * 10 + 1;
111 = 11 * 10 + 1;
1111 = 111 * 10 + 1;
...

위 식으로 예제는 풀수있다. 하지만 예제 외 다른 테스트 케이스에서 시간 초과가 뜬다. 왜냐하면, 1로 이루어진 자리수가 너무 커져 어떤 정수형 데이터 타입으로도 담을 수 없기 때문이다. 이 경우를 해결하기 위해 나머지 연산의 분배법칙을 이용해야한다.

 

두 번째 접근 및 결과

    int div = 0, cnt = 1;
    while (true)
    {
        div = (div * 10 + 1) % n;
        if( div == 0)
            break;
        cnt++;
    }

코드는 크게 바뀌지 않는다. 그냥 식을 % 로 한 번 감싸주면 된다. 이렇게 되면 실제 식은 아래와 같이 적용된다.

1%n = (0*10+1)%n;
11%n = (1*10+1)%n == ((1*10)%n+1%n)%n == ((1%n*10%n)%n+1%n)%n
111%n = (11*10+1)%n == ((11*10)%n+1%n)%n == ((11%n*10%n)%n+1%n)%n
1111%n = (111*10+1)%n == ((111*10)%n+1%n)%n == ((111%n*10%n)%n+1%n)%n
...

식을 풀어보면, 앞번째 값이 이후의 식에 반영됨을 볼 수 있다. 예를 들어, 1111%n의 식에서 111%n이 입력된 부분은 살펴보자. 111%n는 앞서 계산한 값이 대입되었기 때문에 1의 자리수를 이용해 표현하고 있지 않다. 고로 정수 오버플로우는 발생하지 않으며 문제를 풀 수 있게 된다.