[백준] No.11570 - 환상의 듀엣 (C++, DP)

문제

 

https://www.acmicpc.net/problem/11570

11570번: 환상의 듀엣

 

풀이

 

solved.ac 난이도: Platium 5

 

 

 

A(상덕이)가 부른 마지막 음을 a, B(희원이)가 부른 마지막 음을 b라고하자.

dp[a][b]에는 a와 b일때의 힘든정도의 최솟값을 저장하자.

 

이때 현재까지 두 명이 부른 음은 a와 b 중에 더 큰 값(악보상에서 더 뒤에 있는 음)이라고 할 수 있다.

(모든 음은 순서대로 불러야 하므로 이는 성립할 수밖에 없다.)

 

그렇다면 다음으로 불러야 하는 음은 max(a,b) + 1 인 값(next)이다.

A(상덕이)와 B(희원이) 둘 모두 다음 음을 부를 수 있으므로 두 가지 경우를 모두 구해주자.

 

 

1. A가 next음을 부르는 경우

dp[next][b] = min(dp[next][b], dp[a][b] + (a와 next의 음의 차이));

 

2. B가 next음을 부르는 경우

dp[a][next] = min(dp[a][next], dp[a][b] + (b와 next의 음의 차이));

 

 

이를 모든 음인 경우일 때 계산을 해주면 답을 구할 수 있다.

단, 악보의 모든 음을 불렀다면 a와 b 중에 한 값은 마지막 음에 도달해야 하므로 답은 다음과 같이 구할 수 있다.

 

int min_answer = INT32_MAX;
 
//둘 중 하나는 마지막 음까지 불러야 모든 음을 부른게 된다.
for(int i=0; i<=tune_num ; ++i){
  min_answer = min(min_answer, dp[i][tune_num]);
  min_answer = min(min_answer, dp[tune_num][i]);
}

 

어렵다 어려워...

 

참조 풀이

코딩하기 좋은날님의 백준 11570 풀이

 

 

코드