BOJ 백준 11570번 환상의 듀엣

​​

 

BOJ 백준 11570 환상의 듀엣

 

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

11570번: 환상의 듀엣

 

상덕이와 희원이 두 사람이 서로 노래를 부를 때 악보에 적혀 있는 N개의 음을 순서대로 노래한다. 악보에서 서로 인접한 두 음의 높이 차이의 합이 노래를 할 때 힘든 정도이다. 상덕이와 희원이가 한 악보에 있는 N개의 음을 분담하여 노래할 때, 두 사람 각각의 힘든 정도의 합의 최솟값을 구해야 한다.

 

N개의 음을 두 집합 A, B로 나누고 모든 음이 집합 A와 B 중 반드시 하나의 집합에 속할 때, 각 집합의 힘든 정도의 합을 구해서 문제의 정답을 찾을 수 있다. 그런데 naive하게 생각해서 N개의 각 음이 어떠한 집합에 속하는지를 구하면 시간복잡도가 2^N이 되므로 N의 최댓값을 고려할 때 제한 시간 초과가 발생할 수 있다. 따라서 각 사람이 어떠한 음을 노래했는지를 모두 직접 구하는 건 비효율적이다.

 

다이나믹 프로그래밍(Dynamic Programming)을 사용하면 해결이 가능한데, 메모이제이션 할 배열을 어떻게 정의하느냐에 따라 크게 두 가지 방법이 있다.

 

 

 

1. 직전 음을 노래하지 않은 사람이 어떠한 음을 연주했는지를 기준으로 할 때

 

dp[i][j]: 현재 i번째 음을 노래하려고 하는데 직전 음인 i-1번째 음을 노래하지 않은 사람이 j번째 음을 마지막으로 노래했을 때, 두 사람이 힘든 정도의 합의 최솟값

 

‘직전 음을 노래하지 않은 사람이 j번째 음을 마지막으로 노래했을 때’로 정의하지 않고 ‘상덕이가 j번째 음을 마지막으로 노래했을 때’로 정의해버리면 꽤 곤란해진다. 예를 들어, 상덕이가 직전 음인 i-1번째 음을 노래했으면 희덕이가 마지막으로 노래한 음이 어떠한 음인지를 알 수 없다. 그래서 현재 음인 i번째 음을 희덕이가 노래할 경우의 두 사람의 힘든 정도 합의 최솟값을 구할 수 없다.

 

구현의 효율을 위해 top-down 방식을 사용하면 다음과 같은 관계식을 유도할 수 있다.

a[i]: i번째 음의 높이

 

 

1) 직전 음인 i-1번째 음을 노래한 사람이 i번째 음도 노래하는 경우

dp[i][j] = dp[i + 1][j] + |a[i] - a[i - 1]| (단, j < i - 1)

 

 

2) j번째 음을 마지막으로 노래한 사람이 i번째 음을 노래하는 경우

dp[i][j] = dp[i + 1][i - 1] + |a[i] - a[j]| (단, j < i - 1)

 

i-1번째 음을 노래한 사람은 다음에 노래할 때 직전 음을 노래하지 않은 사람이 되므로 dp[i + 1][i - 1]이 된다.

 

 

이 두 경우의 최솟값을 구한다는 점을 반영하여 정리하면 다음과 같다

dp[i][j] = min(dp[i + 1][j] + |a[i] - a[i - 1]|, dp[i + 1][i - 1] + |a[i] - a[j]|) (단, j < i - 1)

 

이를 정리한 코드는 다음과 같다.

 

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N_MAX = 2000;
const long long INF = (long long)1e12;

int n;
long long num[N_MAX + 1];
long long dp[N_MAX + 1][N_MAX + 1];

long long absValue(long long x){
    return (x >= 0) ? x : -x;
}

long long go(int idx, int last){
    // idx번째 음을 연주하려고 하는데
    // 직전 음을 연주하지 않은 사람이 last번째 음을 연주함
    if (idx > n){
        return 0;
    }
    
    long long& ret = dp[idx][last];
    if (ret != -1){
        return ret;
    }
    
    ret = INF;
    // 직전 음을 연주한 사람이 idx번째 음도 연주함
    ret = min(ret, go(idx + 1, last) + ((idx == 1) ? 0 : absValue(num[idx] - num[idx - 1])));
    // 직전 음을 연주하지 않은 사람이 idx번째 음을 연주함
    ret = min(ret, go(idx + 1, idx - 1) + ((last == 0) ? 0 : absValue(num[idx] - num[last])));
    
    return ret;
}

int main(){
    memset(dp, -1, sizeof(dp));
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++){
        scanf("%lld", &num[i]);
    }
    
    printf("%lld\n", go(1, 0));
     
    return 0;
}

 

 

 

 

2. 상덕이와 희원이가 각각 어떠한 음으로 마지막으로 노래했는지를 기준으로 할 때

 

dp[i][j]: 상덕이가 i번째 음을, 희원이가 j번째 음을 마지막으로 노래했을 때, 두 사람의 힘든 정도 합의 최솟값
next: 상덕이와 희원이 둘 중 한 명이 다음에 마지막으로 연주하게 될 음의 서수

 

구현의 효율을 위해 top-down 방식을 사용하면 다음과 같은 관계식을 유도할 수 있다.

next = max(i, j) + 1

 

 

1) 상덕이가 next번째 음을 마지막으로 노래하는 경우

dp[next][j] + |a[next] - a[i]|

 

 

2) 희원이가 next번째 음을 마지막으로 노래하는 경우

dp[i][next] + |a[next] - a[j]|

 

 

정리하면 다음과 같다

dp[i][j] = min(dp[next][j] + |a[next] - a[i]|, dp[i][next] + |a[next] - a[j]|)

 

 

아래 문제도 위와 같은 방법으로 풀이할 수 있다.

 

[BOJ 12932] https://www.acmicpc.net/problem/12932

12932번: 노래방