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

 

출력

각각의 테스트 케이스에 대해 보물의 위치를 $XY$ 형태로 출력한다.

 

예제 출력)

-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에 의해서 $\varphi (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번의 풀이를 마친다.