백준 11570 환상의 듀엣

 

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 주어진 음들이 주어질 때 상덕이와 희원이가 노래를 부릅니다. 이때 이 두사람은 전에 음을 변경할 때 힘이 들게 되는데 이 수치가 abs(현재음-전에불렀던음) 입니다. 이 수치가 최소화 될 수 있는 값을 구해야 합니다. 따라서 dp를 이용하여 모든 경우를 다 해봐야 합니다.

 

dp식을 어떻게 세워야할지 생각해보면 현재 필요한 정보는 두사람이 바로 직전에 불렀던 음에 대한 정보입니다. 따라서 2차원 dp를 선언한다면   dp[i][j] 가 의미하는 바는 상덕이가 마지막으로 부른 음은 i이고 희원이가 마지막으로 부른 음은j라는 의미입니다. 따라서 dp[i][j]를 통해 점화식을 세우면 i와 j중 더큰값에 1을 더하여 next지점을 구한뒤

dp[next][j] = min(dp[next][j],dp[i][j] + abs(umm[next]-umm[i]));
dp[i][next] = min(dp[i][next], dp[i][j] +abs(umm[next] - umm[j]));

이렇게 식을 세울 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <cmath>

using namespace std;
#define MAX 2020
#define INF 2100000000

int dp[MAX][MAX]; // dp[i][j] 의 의미는 i는 상덕이의 마지막 노래 j는 희원이의 마지막 노래
int umm[MAX];

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;

    for(int i = 1; i <= N; i++)
        cin >> umm[i];

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

    dp[1][0] = 0;
    dp[0][1] = 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;

            if(j == 0 || i == 0) umm[0] = umm[next];
            dp[next][j] = min(dp[next][j],dp[i][j] + abs(umm[next]-umm[i]));
            dp[i][next] = min(dp[i][next], dp[i][j] +abs(umm[next] - umm[j]));

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

    }
    cout<<ans;
    return 0;
}