BOJ 1399 - 보물의 위치 (Python3)

어제 수학 레이팅을 올리겠다고 앉은 자리에서 Platinum 수학 문제 두 개를 풀었다. 아뿔싸. Platinum 4부터 레이팅을 올려 준다고 한다. 그냥 Platinum을 두 개 푼 사람이 되어 버렸다.

이 문제는 그 두 문제 중 하나이다. 앉은 자리에서 푸는 데 20분도 걸리지 않았으면 구현은 그렇게 빡세지 않다는 이야기이다. 아이디어가 메인인 문제.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

\(\text{dig}\)라는 함수를 다음과 같이 정의하자.

$$\text{dig}(x) = x\,\,\,\,(0 \le x \le 9)$$ $$\text{dig}(x) = \text{dig}(\text{x의 모든 자리수의 합})\,\,\,\,(x \ge 10)$$

예를 들어, \(\text{dig}(49) = \text{dig}(13) = \text{dig}(4) = 4\)

오민식은 아주 낡은 지도를 가지고 보물을 찾아 헤매는 사냥꾼의 두목이다. 낡은 지도에는 보물을 어떻게 찾아야 하는지가 나와 있다.

지금 오민식은 북쪽을 보고 있고, 현재 좌표는 \((0, 0)\)이다. 북쪽은 \(y\)좌표가 증가하는 방향, 동쪽은 \(x\)좌표가 증가하는 방향이다.

오민식은 다음과 같은 작업을 \(K\)번 반복하면 보물의 위치를 찾을 수 있다. 골드 넘버는 \(1\)부터 시작한다.

1. \(\text{dig}(\text{골드 넘버})\)만큼 앞으로 간다. 그리고 90도 오른쪽으로 회전한다.

2. 골드 넘버에 \(M\)을 곱한다.

오민식의 마지막 위치. 즉, 보물의 위치를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 수 \(T\)가 주어진다. 둘째 줄부터 \(T\)개의 줄에 각각의 테스트 케이스에 대해 \(K\)와 \(M\)이 주어진다. \(K\)는 \(10^9\)보다 작거나 같은 자연수이고, \(M\)은 \(1000\)보다 작거나 같은 자연수이다.

 

예제 입력)

3
5 2
99 1
6 9

 

출력

각각의 테스트 케이스에 대해 보물의 위치를 \(X\,Y\) 형태로 출력한다.

 

예제 출력)

-6 4
1 0
9 1

 

---

내 코드

def move(pos,direc,step):
    if direc == 0: return [pos[0]+step,pos[1]]
    elif direc == 1: return [pos[0],pos[1]-step]
    elif direc == 2: return [pos[0]-step,pos[1]]
    else: return [pos[0],pos[1]+step]
def solve():
    K,M = map(int,input().split()); M = (M-1)%9+1
    step = 1; pos = [0,0]; direc = 3
    if M%3:
        K = (K-1)%12+1
        for _ in range(K):
            pos = move(pos,direc,step)
            step = (step*M)%9; direc = (direc+1)%4
        print(*pos)
    else:
        if K >= 3: K = (K-3)%4+3
        for _ in range(K):
            pos = move(pos,direc,step)
            step = (step*M-1)%9+1; direc = (direc+1)%4
        print(*pos)
for _ in range(int(input())): solve()

 

우선 move(pos,direc,step)은 pos에서 출발하여 direc이 나타내는 방향으로 step만큼 전진한 결과를 내뱉어 준다. direc이 0, 1, 2, 3이면 각각 동, 남, 서, 복쪽으로 전진함을 나타낸다.

우선 \(\text{dig}\) 함수가 대체 뭐 하는 놈인지 알 필요가 있다. 사실 정말 별 것 아니다. 9의 배수이면 9, 9의 배수가 아니면 9로 나눈 나머지를 출력하는 함수이다. \(x\)와 \(x\)의 각 자릿수의 합은 9로 나눈 나머지가 동일하므로, 제법 당연한 일이다.

그러면 dig(골드 넘버)는, \(M\)이 3의 배수가 아닐 때는 Euler's generalization of Fermat's Little Theorem에 의해서 \(\phi(9)=6\)을 주기로 할 것이고 3의 배수이나 9의 배수가 아닐 때는 1 dig(\(M\)) 9 9 9..., 9의 배수일 때는 1 9 9 9 9...가 될 것이다.

 

우선 3의 배수가 아닐 때는 dig(골드 넘버)가 1 a b c d e 1 a b c d e...의 값을 가진다고 하자. 그러면 직접 처음 몇 개의 move를 써 보면 알겠지만, 12개의 move를 주기로 가진다. 따라서 K를 12로 나눈 나머지만큼만 move를 해 주면 된다.

3의 배수일 경우는 처음 두 항을 제외하고는 4개의 move를 주기로 가진다. 따라서 K가 1 혹은 2일 경우 예외처리를 해 주고, 그렇지 않을 경우 K를 4로 나눈 나머지에 4를 더하거나, 아니면 4로 나눈 나머지가 같은 3 이상의 수인 (K-3)%4 + 3을 새로운 K로 두고 그만큼의 move를 구현만 하면 된다.

한 번 move할 때마다 방향이 북 동 남 서 순으로 바뀌므로, direc에 1을 더해주고 4로 나눈 나머지를 취하는 것을 잊지 말자.

 

이로서 1399번의 풀이를 마친다.