보드 게임 - SDS_PRO_7_3

문제 링크(koitp.org/problem/SDS_PRO_7_3/)

동적계획법으로 풀 수 있다.

D(i, j) : i번 카드까지 사용했고, 마지막에 j번 마을에 있었을 때의 최적해

j번 마을에 붙어있는 간선 j-k를 통해서 D(i-1, k)로 점화관계를 세울 수 있다.

D(i, j) = max[D(i-1, k) + 10*(i번 카드 색깔== 간선 j-k의 색깔)]