(C++) 백준 11570 환상의 듀엣

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

공포의 dp ...😨😨😨 ㅠ 너무 싫다 하지만 푼다 ..

dp 테이블은 dp[i][j] : 상덕이가 마지막으로 i, 희원이가 마지막으로 j 번째 음을 불렀을 때 가질수 있는 최소값 으로 정의했다. 상덕이와 희원이가 같은 음을 부를 수 없으므로 같은 경우는 제외한다.

테이블을 돌며 갱신하는 값은 그 다음으로 불러야 하는 값 이다. max(i,j)중 더 큰 값 까지는 누군가 부른것이므로.. 그 다음 음인 max(i,j)+1 에 대해 값을 구할 수 있다.

이때 기존에 구해진 값과 다음 음을 불렀을 때 계산한 값 dp[i][j]+abs(i==0?0:arr[i]-arr[next]) 을 비교하여 더 작은 값으로 갱신한다.

    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            if(i==j) continue;

            int next = max(i, j) +1;
            dp[next][j] = min(dp[next][j], dp[i][j]+abs(i==0?0:arr[i]-arr[next]));
            dp[i][next] = min(dp[i][next], dp[i][j]+abs(j==0?0:arr[j]-arr[next]));

        }
    }

• 전체코드

#include <iostream>
#include <cstring>
using namespace std;


int N;
int arr[2005];
int dp[2005][2005];

const int INF = 2000000000;

int main(){
    cin>>N;

    for(int i=1; i<=N; i++) cin>>arr[i];
    for(int i=0; i<=N; i++) for(int j=0; j<=N; j++) dp[i][j] = INF;
    dp[0][1]=dp[1][0]=0;

    for(int i=0; i<=N; i++){
        for(int j=0; j<=N; j++){
            if(i==j) continue;

            int next = max(i, j) +1;
            dp[next][j] = min(dp[next][j], dp[i][j]+abs(i==0?0:arr[i]-arr[next]));
            dp[i][next] = min(dp[i][next], dp[i][j]+abs(j==0?0:arr[j]-arr[next]));

        }
    }

    int ans=INF;
    for(int i=0; i<N; i++){
        ans = min(ans, dp[N][i]);
    }

    cout<<ans;

}