[Python 3] BOJ - 13392 "방법을 출력하지 않는 숫자 맞추기"

 # 문제 링크

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

13392번: 방법을 출력하지 않는 숫자 맞추기

 

 # 풀이

 개인적으로 이 문제의 핵심은 다이나믹 프로그래밍이라고 생각한다. 상태 공간을 현재 idx번째 인덱스이고 위에서 부터 왼쪽으로 left번만큼 돌렸을 때 목표 숫자를 맞추기 위한 최소 움직임인 dp[idx][left]라고 정의하자. 자칫 상태 공간이 메모리 초과에 걸릴만큼 크다고 생각할 수 있으나, 위칸에서 왼쪽으로 얼마나 많이 돌릴지라도 10칸을 돌린다면 제자리가 되기 때문에 실제로 left는 0이상 10미만의 값을 갖는다. 따라서, 상태공간을 충분히 메모리 제한 내에 만들 수 있다

 또한 현재 수가 3이고 맞춰야 하는 수가 7이라면 굳이 맞춰야 하는 수인 7이 아닌 수로 맞추는 것은 의미가 없다. 따라서, 현재 수가 정의되었을 때 맞춰야 하는 수를 맞추기 위해 왼쪽으로 몇번을 가야하고, 오른쪽으로 몇번을 가야하는지만 알면 된다. 따라서 이것을 빠르게 구하기 위해 현재 수가 i이고 맞춰야 하는 수가 j일 때 오른쪽 혹은 왼쪽으로 몇 칸 움직여야 하는지를 저장하는 2차원 배열을 미리 계산하면 된다.

 점화식은 현재 상태 공간에서 왼쪽으로 움직이거나, 오른쪽으로 움직이거나 두 가지 경우가 있다. 따라서 현재 수가 now이고 맞춰야 하는 수가 next, 다음번 왼쪽으로 돌릴 횟수를 next_left라고 할 때 점화식은 아래와 같다. $$ \begin{cases} dp[idx][left] = min(dp[idx][left], \ dp[idx + 1][next\_left \ \% \ 10] + left\_cache[now][next] \ \% \ 10) \\ dp[idx][left] = min(dp[idx][left], dp[idx + 1][left] + right\_cache[now][next]) \end{cases} $$

 

 # 코드

import sys

# 재귀깊이해제
sys.setrecursionlimit(100000)

# go : 현재 idx번째 인덱스이고 위층에서 전체 left만큼 돌렸을 때 목표 숫자를 맞추기 위해 필요한 최소 조작 수를 리턴하는 함수
def go(idx, left):
    # Base Case : 모두 돌린경우
    if idx == n:
        return 0
    # Memoization
    if dp[idx][left] != -1:
        return dp[idx][left]
    dp[idx][left] = 9876543210
    # 위층에서 돌린 만큼 현재 숫자 재정의
    if left:
        now = (arr[idx] + left) % 10
    else:
        now = arr[idx]
    # 점화식
    dp[idx][left] = min(dp[idx][left], go(idx + 1, (left + left_cache[now][res[idx]]) % 10) + left_cache[now][res[idx]])
    dp[idx][left] = min(dp[idx][left], go(idx + 1, left) + right_cache[now][res[idx]])
    return dp[idx][left]

# left_cache : 현재 수가 i, 맞춰야 하는 수가 j일 때 왼쪽으로 몇칸 돌려야 하는지를 저장하는 2차원 배열
left_cache = [[-1] * 10 for _ in range(10)]

# right_cache : 현재 수가 i, 맞춰야 하는 수가 j일 때 오른쪽으로 몇칸 돌려야 하는지를 저장하는 2차원 배열
right_cache = [[-1] * 10 for _ in range(10)]
for i in range(10):
    for j in range(10):
        temp = 0
        while True:
            if (i + temp) % 10 == j:
                break
            temp += 1
        left_cache[i][j] = temp
        temp = 0
        while True:
            if (i - temp) % 10 == j:
                break
            temp += 1
        right_cache[i][j] = temp

# 입력부 및 정답출력
n = int(sys.stdin.readline())
dp = [[-1] * 10 for _ in range(n)]
arr = list(map(int, sys.stdin.readline().rstrip()))
res = list(map(int, sys.stdin.readline().rstrip()))
print(go(0, 0))