BOJ 11570 : 환상의 듀엣
2021. 4. 30. 09:40ㆍPS/DP
dp로 풀 수 있다.
dp[i][j] = i번째 음을 이가, j번째 음을 이가 불렀을때 최적해
A_i = i번째 음을 부를때 비용
nxt = 불러야 할 음
이라고 정의할 때,
dp[i][nxt] = min(dp[i][j] + |A_nxt - A_j|, dp[i][nxt])
dp[nxt][j] = min(dp[i][j] + |A_nxt - A_i|, dp[nxt][j])
코드
'PS > DP' 카테고리의 다른 글
BOJ 20984 : Growing Vegetables is Fun 4 (0) | 2021.05.11 |
---|---|
BOJ 2618 : 경찰차 (1) | 2021.04.30 |
BOJ 14728 : 벼락치기 (0) | 2021.01.10 |
BOJ 2688 : 줄어들지 않아 (0) | 2020.08.17 |
BOJ 17623 : 괄호 (0) | 2020.08.17 |