환상의 듀엣 C++ - 백준 11570

https://acmicpc.net/problem/11570

DP 문제.

문제 접근

DP 문제를 접하게 되면 처음에는 일차원 배열 DP를 배우게 된다.

하지만 DP 방법론 특성상 다양한 형태의 점화식이 가능하기 때문에

DP 문제를 일차원 배열로 푼다는 생각은 내려두고 접근해야 한다.

이 문제도 위와 같다.

처음에는 그리디하게

양쪽 팀에게 음을 배분하고 그것을 DP적으로 해결한다고 생각했지만

이는 틀렸다.

새로운 DP 점화식이 필요했다.

! 다른 방식으로 생각해보자 !

노래가 끝나는 경우는 어떤 한 사람이 마지막 음을 부르는 경우이다.

이에 여러 경우의 수가 존재하는데 그것은 다음과 같다.

상덕이를 0으로 두고 희원이를 1로 둘 때,

0이 $n$번째음을 부를 때,

1은 하나도 부르지 않는 것,

1을 마지막으로 부르는 경우,

n-1번째를 마지막으로 부르는 경우를 살펴볼 수 있다.

이 점화관계에서 $DP(i,j)$를 0이 $i$음을 마지막으로 부르고,

1이 $j$음을 마지막으로 불렀을 때 최소 비용이라고 하자.

그 다음 음을 $nw=max(i,j)+1$라고 할때 0이 부를 수도

1이 부를 수도 있는 경우를 모두 고려해야 한다.

그러면 다음과 같은 점화식이 도출된다.

$DP(nw,j)=min(DP(i,j)+abs(a[nw]-a[i]),DP(nw,j))$
$DP(i,nw)=min(DP(i,j)+abs(a[nw]-a[j]),DP(i,nw))$

이다.

기본 초항인 $DP(0,1),DP(1,0)$을 채우고 나서 위 점화식을 돌려주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n;
vector<ll> a;
vector<vector<ll>> dp;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    a.resize(n+1);
    dp.resize(n+1,vector<ll> (n+1,INT32_MAX));
    for(int i=1;i<=n;i++) cin >> a[i];
    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 nw=max(i,j)+1;
        if(i==0 || j==0) a[0]=a[nw];
        dp[nw][j]=min(dp[nw][j],dp[i][j]+abs(a[i]-a[nw]));
        dp[i][nw]=min(dp[i][nw],dp[i][j]+abs(a[j]-a[nw]));
    }
    ll ans=INT32_MAX;
    for(int i=0;i<n;i++) ans=min(ans,min(dp[n][i],dp[i][n]));
    cout << ans;
    return 0;
}