[자바로 푸는 백준] 11570번 환상의 듀엣

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

11570번: 환상의 듀엣

✅ 플래티넘 Ⅴ

 

🔶 풀이

내가 선택한 플래티넘 문제는 개인적으로 가장 어려워하는 dp..

음의 차이를 나타내는 힘든 정도의 최솟값을 구하라.

 

문제의 이해를 돕기 위해 편의상 상덕이를 A, 희원이를 B로 하겠다.

dp 배열은 각자 마지막으로 부른 음을 기준으로 힘든 정도의 최솟값을 저장해줬다.

 

현재 상태: dp[A가 마지막으로 부른 음][B가 마지막으로 부른 음];

A가 다음으로 부를 경우: dp[next][B];

B가 다음으로 부를 경우: dp[A][next];

 

여기서 다음 음을 나타내는 next는 A와 B가 부른 마지막 음에서 높은 음을 선택 후에 + 1을 해주면 된다.

즉, Math.max(A, B) + 1 이다.

 

next 음을 설정해줬다면 A가 부를 경우, B가 부를 경우 중 최솟값을 찾아야된다.

if (i == 0 || j == 0) Music[0] = Music[next]; // 0번째 음을 불렀을 경우에는 값이 0이므로 힘든 정도는 0이다.
dp[next][j] = Math.min(dp[next][j], dp[i][j] + Math.abs(Music[i] - Music[next])); // A가 다음으로 부를 경우 (A == i)
dp[i][next] = Math.min(dp[i][next], dp[i][j] + Math.abs(Music[j] - Music[next])); // B가 다음으로 부를 경우 (B == j)

A가 다음으로 부를 경우는 dp[next][B]이고, 현재 상태는 dp[A][B]다.

힘든 정도는 현재 부른 음에서 다음으로 부를 음의 차이이기 때문에 Music[A] 에서 Music[next]를 빼주면 된다.

 

위 방식으로 dp 배열을 전부 채웠다면 마지막으로 노래를 다 불렀을 때, 힘든 정도의 최솟값만 찾아주면 된다.

노래를 다 불렀다는 의미는 A와 B중 한 사람은 마지막 음을 불렀다는 뜻으로 아래와 같이 표현할 수 있다.

int ans = Integer.MAX_VALUE;
for (int i=0; i<N; i++) {
    ans = Math.min(ans, dp[i][N]);
    ans = Math.min(ans, dp[N][i]);
}

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int N = Integer.parseInt(br.readLine());
		
        int[] Music = new int[2001];
		
        st = new StringTokenizer(br.readLine());
        for (int i=1; i<=N; i++) {
            Music[i] = Integer.parseInt(st.nextToken());					
        }
		
        int[][] dp = new int[2001][2001];
		
        for (int i=0; i<=N; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
		
        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; // 같은 음은 볼 필요 X
                int next = Math.max(i, j)+1; 
				
                // ArrayIndexOutOfBounds 에러 방지
                if (next > N) continue;
				
                
                if (i == 0 || j == 0) Music[0] = Music[next]; // 0번째 음을 불렀을 경우에는 값이 0이므로 힘든 정도는 0이다.
                dp[next][j] = Math.min(dp[next][j], dp[i][j] + Math.abs(Music[i] - Music[next])); // A가 다음으로 부를 경우 (A == i)
                dp[i][next] = Math.min(dp[i][next], dp[i][j] + Math.abs(Music[j] - Music[next])); // B가 다음으로 부를 경우 (B == j)
            }
        }
		
        // 노래를 끝냈다는 뜻은 두 사람 중 한 명이 마지막 음을 불렀다는 뜻
        int ans = Integer.MAX_VALUE;
        for (int i=0; i<N; i++) {
            ans = Math.min(ans, dp[i][N]);
            ans = Math.min(ans, dp[N][i]);
        }
		
        System.out.println(ans);
    }
}