[Algo] 백준 25049 뮤직 플레이리스트 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/25049

메모리 : 86404KB

시간 : 496ms

언어 : Java 11

---

코드

import java.beans.IntrospectionException;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        long ans = 0;
        long[] arr = new long[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
            // 일단 전곡을 1회는 들어야하기 때문에 누적합 더해주기
            ans += arr[i];
        }
        long[] Ldp = new long[N];
        long[] maxLdp = new long[N];
        maxLdp[0] = Ldp[0] = arr[0];
        for (int i = 1; i < N; i++) {
            // 전칸이 최대부분합으로 이어지는지, 새로 끊어가야하는지 판단
            Ldp[i] = Math.max(Ldp[i - 1] + arr[i], arr[i]);
            // 최대부분합을 구해주기
            maxLdp[i] = Math.max(maxLdp[i - 1], Ldp[i]);
        }
        long[] Rdp = new long[N];
        long[] maxRdp = new long[N];
        maxRdp[N - 1] = Rdp[N - 1] = arr[N - 1];
        for (int i = N - 2; i > 0; i--) {
            Rdp[i] = Math.max(Rdp[i + 1] + arr[i], arr[i]);
            maxRdp[i] = Math.max(maxRdp[i + 1], Rdp[i]);
        }
        long maxsum = 0;
        // 전곡 다시듣기가 더 좋을지도?
        maxsum = Math.max(0, maxLdp[N - 1]);
        for (int i = 0; i < N - 2; i++) {
            maxsum = Math.max(maxsum, maxLdp[i] + maxRdp[i + 1]);
        }
        ans += maxsum;
        System.out.println(ans);
    }
}

풀이

너무 어려운 문제였다ㅜ

1. 부분합 중 최댓값을 구해야 한다.
2. 노래는 두 번 돌아갈 수 있기 때문에 두 개 구해야 한다.
3. 최댓값 두 개를 다른 부분에서 어떻게 구할까?
   1. 왼쪽에서 본 부분합최댓값과 오른쪽에서 본 부분합최댓값을 구하면 된다
   2. 왜 ???? 왼쪽과 오른쪽이 겹칠 수 없기 때문에 왼쪽 최댓값과 오른쪽 최댓값은 서로를 밀어내며 부분최대값 두개를 찾아야 한다.
4. 양쪽의 최댓값을 더한 값 중에 또 최대를 찾아 답에 더한다.

왼쪽과 오른쪽의 부분합최댓값을 구하는 것에 카데인 알고리즘이 필요하다. 원래 최대 부분합을 구하려면 브루트포스로 완전탐색해야하는데, 이런 경우에 시간복잡도가 O(N^2)이기 때문에 O(N)으로 풀려면 카테인알고리즘을 사용해야한다.

Ldp[i] = Math.max(Ldp[i - 1] + arr[i], arr[i]);

부분합을 구해가면서 현재 칸(i)이 전부터 이어저오는 부분에 속하는것이 이익인지, i부터 새 부분합을 시작하는 것이 이익인지 결정해야 한다. dp[i]=Math.max(전칸까지의 부분합+현재칸 , 현재칸)