BOJ_7412_환상의 듀엣 (Java)

[Platinum V] 환상의 듀엣 - 11570 Add commentMore actions

문제 링크

성능 요약

메모리: 52332 KB, 시간: 296 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 6월 3일 04:12:42

문제 설명

상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높이가 순서대로 N개 적혀져 있었다. 둘은 악보에 적혀 있는 모든 음들을 노래해야 하며, 각 음은 둘 중 한 사람에 의해서만 불러져야 한다. 예를 들어 악보에 {3, 6, 2, 5, 4}가 적혀져 있을 때, 상덕이가 {3, 2, 4}을 노래하면 희원이는 {6, 5}를 노래할 것이고, 상덕이가 {6, 2, 5}을 노래하면 희원이는 {3, 4}를 노래할 것이다.

노래를 부르다 음의 높이를 변경하는 것은 힘든 일이다. 예를 들어 {4, 6}을 부르는 것은 {4, 4}를 부르는 것에 비해서 음의 변경이 발생하기 때문에 더 힘들다고 볼 수 있다. 희원이는 {a₁, a₂, ..., a_k}라는 음들의 집합을 노래할 때 힘든 정도를 |a₁ - a₂| + |a₂ - a₃| + ... + |a_k-1 - a_k|로 정의했다. 노래를 부르는 사람은 상덕이와 희원이 둘 뿐이므로, 음들을 집합은 두 개가 있을 것이다. 따라서 두 사람이 해당 악보를 노래를 할 때 힘든 정도는 두 집합의 힘든 정도의 합으로 표현될 수 있다.

상덕이와 희원이는 해당 악보를 노래할 때 힘든 정도를 최소화하고 싶다. 예를 들어 악보가 {1, 3, 8, 12, 13}으로 주어진다하자. 앞의 2개를 상덕이가 부르고 뒤의 3개를 희원이가 부르게되면 상덕이의 힘든 정도는 |1 - 3| = 2, 희원이의 힘든 정도는 |8 - 12| + |12 - 13| = 5가 되며 합인 7이 총 힘든 정도가 되고, 이 값은 나올 수 있는 힘든 정도 중에 가장 최솟값이다. 상덕이와 희원이를 위해서 해당 악보를 노래할 때 힘들 수 있는 정도의 최솟값을 알려주는 프로그램을 작성해보자.

입력

첫 번째 줄에는 음의 개수 N (1 ≤ N ≤ 2,000)이 주어진다.

두 번째 줄에는 N개의 음의 높이가 공백(빈 칸)으로 구분되어 주어진다. 각 음의 높이의 범위는 1 이상 1,000,000 이하의 자연수이다.

출력

상덕이과 희원이가 해당 악보를 노래할 때 힘들 수 있는 정도의 최솟값을 출력한다.

문제 풀이

dp 설계가 중요.

dp[i][j] = 상덕이가 마지막으로 i까지 부르고 희원이가 마지막으로 j까지 불렀을 때 최솟값

코드

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

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int[] music;
    static long[][] dp;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        music = new int[N+1];
        dp = new long[N+1][N+1];

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            music[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<=N; i++){
            for(int j=0; j<=N; j++){
                dp[i][j] = 2_000_000_000;
            }
        }

        dp[0][0] = 0;
        dp[1][0] = 0;
        dp[0][1] = 0;
        for(int i=2; i<=N; i++){
            dp[i][0] = dp[i-1][0] + Math.abs(music[i] - music[i-1]);
            dp[0][i] = dp[0][i-1] + Math.abs(music[i] - music[i-1]);
        }

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

                if(i==j) continue;

                if((Math.max(i, j) + 1) > N) continue;

                if(i==0 || j == 0) {
                    music[0] = music[Math.max(i, j) + 1];
                    dp[Math.max(i, j) + 1][j] = Math.min(dp[Math.max(i, j) + 1][j], dp[i][j] + Math.abs(music[Math.max(i, j) + 1] - music[i]));
                    dp[i][Math.max(i, j) + 1] = Math.min(dp[i][Math.max(i, j) + 1], dp[i][j] + Math.abs(music[Math.max(i, j) + 1] - music[j]));
                }
                else {
                    dp[Math.max(i, j) + 1][j] = Math.min(dp[Math.max(i, j) + 1][j], dp[i][j] + Math.abs(music[Math.max(i, j) + 1] - music[i]));
                    dp[i][Math.max(i, j) + 1] = Math.min(dp[i][Math.max(i, j) + 1], dp[i][j] + Math.abs(music[Math.max(i, j) + 1] - music[j]));
                }
            }
        }

        long res = 2_000_000_000;
        for(int i = 0; i < N; i++){
            res = Math.min(res, dp[i][N]);  // 한명 N번째 곡까지
            res = Math.min(res, dp[N][i]);  // 다른 한명 N번째 곡까지
        }

        System.out.println(res);

//        for(int i=0; i<=N; i++){
//            System.out.println(Arrays.toString(dp[i]));
//        }
        br.close();
    }
}