BOJ 11570 : 환상의 듀엣
2021. 4. 30. 09:40ㆍPS/DP
11570번: 환상의 듀엣
상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높
www.acmicpc.net
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])
코드
djayy035/dj035_PS
코드저장소. Contribute to djayy035/dj035_PS development by creating an account on GitHub.
github.com
'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 |