cdjs의 코딩 공부방

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

1. 문제

- dig라는 함수를 다음과 같이 정의하자.

$dig(x) = x(0 \leq x \leq 9)$

$\cdot dig(x) = dig(x의  모든  자리수의  합) (x \geq 10)$

- 각 테스트케이스에 $M$, $K$가 주어진다. ($M \leq 1,000 , K \leq 10^9$)

- 초기에 (0, 0)에서 북쪽을 바라보고 있으며 초기값이 1인 골드 넘버 대해, $dig(골드 넘버)$만큼 앞으로 가고 90도 오른쪽으로 회전한 뒤, 골드 넘버에 $M$을 곱하는 것을 $K$회 반복한다.

- 위 작업을 실시했을 때 최종 위치는 어디인가?

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

3-1. 문제 관찰 과정 및 풀이

처음 문제를 보면, $K$의 값이 너무나도 크기 때문에 직접 돌려보는 것은 아예 불가능하다는 것을 파악할 수 있다.

따라서, 반드시 반복 횟수를 줄일 수 있는 수학적 방법이 존재함을 고려할 수 있다.

우선 첫 번째 예제 케이스를 직접 계산해 보면서 규칙을 찾아보자.

$K=5, M=2$인 상황에서 골드 넘버는 $1, 2, 4, 8, 16$이 되고, $dig(x) = 1, 2, 4, 8, 7$이 된다.

뭔가 부족하니까 K를 늘려서 조금 더 관찰해 보자.

골드 넘버가 $1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024$일때, $dig(x) = 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 7$이 된다.

...왠지 모르게 숫자가 반복된다는 점을 파악할 수 있지만, 이것만으로는 풀이가 불완전하다.

반복이 일어난다면 어째서 반복이 일어나는지를 파악해야 하므로, 우선 $K$를 획기적으로 줄일 수 있는 방법이 있다는 믿음을 가지고 삽질을 시작하자.

우선 $dig$의 정의는 숫자 각 자리의 합으로 이루어져 있다는 것을 확인할 수 있다.

그러면 $dig(x)$와 $dig(x*M)$의 관계성을 분석하기 위해선, $x$와 $x*M$의 각 자리의 합을 생각해야 한다.

$x$의 각 자리수를 분해하여 $x$를 $a + 10b + 100c + \dots $라고 하면, $x*M = a*M + b*M + c*M + \dots$ 라는 사실은 쉽게 확인할 수 있다.

그런데 $dig(x) = a + b + c + \dots$이고, $x*M = a*M + b*M + c*M + \dots$이므로 $dig(dig(x)*M) = dig(x*M)$이라는 사실을 확인할 수 있다!

또한, 위 성질을 연장하여 $dig(dig(dig(x)*M)*M) = dig(dig(x*M)*M)$라는것 또한 알 수 있으므로, 어떤 $x$에 대해서도 $dig(x*M^y)$의 계산에서 $M$을 $K$번 곱하지 않고도 구할 수 있음을 확인할 수 있다.

다음은 $dig(x)$의 값이 반드시 0 이상 9 이하라는 점에서 주목해 보자.

$dig(dig(x)*M) = dig(x*M)$의 성질에서 파악 가능하듯, $dig(x*M)$의 값은 $dig(x)$값만 알아도 구할 수 있는데, $dig(x)$의 값은 0 이상 9 이하이므로 어떤 수 $M$에 대해 $dig(x*M)$의 값은 $dig(x)$의 열가지 경우의 수에 대해서만 결정된다.

(TMI: 물론 $dig(x)$의 정의에 의해 $dig(x)$가 0이 되는 일은 없어서 아홉 가지 경우의 수밖에 없긴 하다)

가령, $M=2$에 대해 그 어떤 $x$에 대해서도 $dig(x)=1$이면 $dig(x*M)=2$, $dig(x)=5$이면 $dig(x*M)=1$과 같이 결정된다는 것이다.

이에 따라 반드시 $dig(x) = dig(x*M^y)$인 지점이 생기게 되므로 반복하는 구간이 생기게 되고, 이 주기는 비둘기집의 원리에 의해 최대 10이 된다.

이제 이 주기에 따라 $K$값을 줄여주는 구현을 하면 되는데, 이 구현을 생각하기가 조금 까다로울 수 있다.

필자의 경우, queue에 값을 계속 넣어주다가 이미 들어온 적 있는 값이 queue에 들어오면 해당 값이 front에 올때까지 pop해준 뒤, $K %= 해당 queue의 길이 * 4$ 연산으로 $K$값을 줄여주었다.

이렇게만 줄이더라도 queue의 길이는 최대 10이라는 사실을 파악했으므로 $K$는 40 이하가 되고, 40번까지는 충분히 브루트 포스로 돌릴 수 있으므로 그대로 구현하면 된다.

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int dig(int x) {
    if (x<10)   return x;
    int sum = 0;
    while (x>0) {
        sum += x%10;
        x/=10;
    }
    return dig(sum);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        queue<int> q;
        int k, m;
        int y=0, x=0;
        int dir = 0;
        cin >> k >> m;
        vector<int> visited(10, 0);
        int num = 1;
        while (k>0) {
            if (visited[num]) {
                while (q.front() != num) {
                    q.pop();
                }
                k%=(4*q.size());
                if (k==0)   break;
            }
            visited[num] = 1;
            q.push(num);
            switch(dir) {
                case 0:
                    y+=num;
                    break;
                case 1:
                    x+=num;
                    break;
                case 2:
                    y-=num;
                    break;
                case 3:
                    x-=num;
                    break;
            }
            k--;
            num = dig(num*m);
            dir = (dir+1)%4;
        }
        cout << x << " " << y << "\n";
    }
}

5. 여담

처음에 $K$ 나머지 연산할 때 0이어도 계속 진행되게 코드를 구현해서 WA를 띄웠었다.

대회에서 신나게 풀어놓고 저렇게 실수해서 패널티 쌓이면 상당히 슬프겠는데....