[백준 2494번] 숫자 맞추기 (Python3)

N = int(input())
data1 = [*map(int,input())]
data2 = [*map(int,input())]

DP = [[0]*10 for i in range(N+1)]
path = [[0]*10 for i in range(N+1)]

for n in range(N):
  n = N-1-n
  for i in range(10):
    d = (data2[n]-data1[n]-i)%10
    l,r = d+DP[n+1][(d+i)%10],10-d+DP[n+1][i]
    if l<r:
      DP[n][i],path[n][i] = l,d
    else:
      DP[n][i],path[n][i] = r,d-10

print(DP[0][0])
i = 0
for n in range(N):
  c = path[n][i]
  print(n+1,c)
  if c>0:
    i = (c+i)%10

방법을 출력하지 않는 숫자 맞추기 [백준 13392번] 방법을 출력하지 않는 숫자 맞추기 (Python3) (tistory.com) 에서 방법을 출력하는 문제이다.

 

풀이과정은 그냥 똑같고, 경로에 대한 배열만 추가해주면 된다.

 

DP를 갱신할 때, min으로 갱신하지 않고 if else로 대소관계를 비교한 후, 왼쪽으로 돌리는 경우 양수로, 오른쪽으로 돌리는 경우 음수로 기록한다. 그리고 출력할 때, path 배열의 값이 음수면 그대로, 양수면 i값을 돌린 횟수만큼 더해주면 된다.

 

 

오늘의 교훈) DP문제는 재미있다.