[boj 2494] 숫자 맞추기

문제 링크

 

dp로 풀어야 한다는건 알겠는데, 복원하는 과정에서 애를 먹었습니다.

 

복원하면서 알게된 점은, 최적해에서는 하나의 나사에서 왼쪽으로 돌렸다가 오른쪽으로 돌렸다가 하는 상황을 생각할 필요가 없다는 점 입니다. 왼쪽 회전은 위로, 올릴 수 있기 때문에 잘 나눠져서, 한 나사에서 하나의 행동을 하는 상태가 최적 상태이기 때문이죠.

 

import sys
input = sys.stdin.readline


def solve():
    N = int(input())
    cur = list(map(int, list(input().rstrip())))
    tar = list(map(int, list(input().rstrip())))
    
    
    dp = [[float("inf")] * 10 for _ in range(N+1)]
    trace = [[0] * 10 for _ in range(N+1)]
    
    for i in range(10): dp[0][i] = i
    
    # dp[i][j] i: 숫자나사 순서 j: 총 왼쪽으로 돌린 횟수 dp[i][j]: 총 회전 수
    
    for i in range(1, N+1):
        for j in range(10):
            for k in range(10):
                l = (j - k + 10) % 10
                cur_n = (cur[i-1] + j) % 10
                diff = (cur_n - tar[i-1] + 10) % 10
                
                if dp[i-1][k] + diff + l < dp[i][j]:
                    dp[i][j] = dp[i-1][k] + diff + l
                    trace[i][j] = k

    ans = []
    min_val = min(dp[-1])
    print(min_val)
    
    cur_idx = dp[-1].index(min_val)
    
    ans.append(cur_idx)
    for idx in range(N, 1, -1):
        cur_idx = trace[idx][cur_idx]
        ans.append(cur_idx)
    
    acc = 0
    idx = 0
    while ans:
        a = ans.pop()   # 현재 위치까지 처리한 뒤의 누적 왼쪽 회전량
        left = (a - acc + 10) % 10
        right = ((cur[idx] + a) % 10 - tar[idx] + 10) % 10

        if left > 0:
            print(idx + 1, left)
        else:
            print(idx + 1, -right)

        acc = a
        idx += 1
    
    return


def main():
    solve()
    
    return


if __name__ == "__main__":
    main()