N = int(input())
d1 = [*map(int,input())]
d2 = [*map(int,input())]
DP = [[0]*10 for i in range(N+1)]
for n in range(N):
n = N-1-n
for i in range(10):
d = (d2[n]-d1[n]-i)%10
DP[n][i] = min(d+DP[n+1][(d+i)%10],10-d+DP[n+1][i])
print(DP[0][0])재미있는 DP 문제였다.
아이디어를 떠올리기가 생각보다 쉽지 않았다.
핵심은 경우의 수를 10가지로 축약하는 것이다.
n번째 숫자를 돌린다고 가정하자. 이때 0~n-1번째 숫자들을 왼쪽으로 돌린 횟수의 총 합을 X번이라고 하자. 그러면 현재 위치의 숫자는 (원래숫자 + X)를 10으로 나눈 나머지가 된다. 이 나머지 값을 x라고 하면, x의 가짓수는 0~9 총 10개이다. 이 10개의 경우의 수에 대해서 가장 아랫줄부터 Top-down 방식으로 돌린 횟수의 최솟값을 채워나가면 된다.
즉 DP[n][i]는 "n번째 숫자 이전에 왼쪽으로 돌린 횟수를 10으로 나눈 나머지가 i일 때, 현 상태에서 n번째 이후의 숫자들을 원하는 숫자로 만드는 데 필요한 최소횟수" 를 의미한다.
여담) 내 풀이가 이 문제 숏코딩 랭킹 1위가 되었다!
