🚀 백준 13398: 연속합 2 문제 해결 후기

이번 포스팅에서는 백준 13398번: 연속합 2 문제를 해결하면서 겪었던 시행착오와 개선 과정을 공유하고자 함. ✨

---

📌 문제 개요

문제에서는 n개의 정수로 이루어진 수열이 주어짐.
연속된 구간의 합 중 최대값을 구해야 하는데, 단 한 개의 원소를 제거할 수 있는 조건이 추가됨. 😲
(단, 적어도 한 개의 원소는 선택해야 함!)

예를 들어,

• 입력: 10 -4 3 1 5 6 -35 12 21 -1
• 출력: 54
  → -35를 제거했을 때 최대 연속합이 54가 됨. 🎯

---

❌ 초기 접근: 누적합(Prefix Sum) 방식의 한계

처음에는 누적합(Prefix Sum)을 이용해 연속 구간의 합을 빠르게 계산하려고 함.
누적합을 사용하면

[
P[i] = arr[1] + arr[2] + \cdots + arr[i]
]

로 구간 합을

[
P[j] - P[i-1]
]

로 빠르게 계산할 수 있음.

🔻 하지만 한 개의 원소 제거 조건을 처리하려고 할 때, 예상치 못한 문제가 발생함.

⚠️ 문제점

누적합을 사용하면 연속 구간의 합을 쉽게 구할 수 있지만, 구간 내 특정 원소를 제거하는 방법이 너무 복잡해짐.

• 원소를 제거하는 경우의 수를 모두 고려하려면 O(n²) 이상의 시간 복잡도가 필요함.
• n이 최대 100,000이라서 시간 초과 가능성이 큼.

💡 결국 누적합만으로는 "제거" 조건을 효율적으로 반영하기 어려움이라는 결론에 도달함.

---

✅ 동적 계획법(DP) 접근

💡 문제 해결의 핵심은 한 개의 원소를 제거하는 경우와 그렇지 않은 경우를 동시에 고려하는 것임.
따라서, DP 배열을 두 가지 상태로 관리함. 📊

• dp[i][0]: 인덱스 i까지 고려했을 때, 아직 원소 제거를 사용하지 않은 상태에서 끝나는 연속 부분합의 최대값
• dp[i][1]: 인덱스 i까지 고려했을 때, 이미 한 개의 원소를 제거한 상태에서 끝나는 연속 부분합의 최대값

---

🔢 DP 점화식

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

✔ dp[i][0]
기존의 카데인 알고리즘(Kadane's Algorithm)과 동일하게, 현재 원소를 포함할 때

• 이전 연속합에 더하거나
• 현재 원소로 새롭게 시작하는 두 가지 경우 중 최댓값을 선택함.

✔ dp[i][1]

• 아직 제거하지 않은 상태(dp[i-1][0])에서 현재 원소를 제거하는 경우
• 이미 제거한 상태(dp[i-1][1])에서 현재 원소를 계속 더하는 경우

이 두 가지를 비교하여 최댓값을 갱신함.

---

⚡ 초기화 문제: dp[0][0]의 중요성

코드를 처음 작성할 때, dp[0][0]을 올바르게 초기화하지 않아서 오답이 발생함. 😵‍💫

❌ 문제 상황

dp[0][0]에 초기값을 넣지 않으면

dp[1][0] = Math.max(dp[0][0] + arr[1], arr[1]);

에서 올바른 비교가 이루어지지 않음.

✅ 해결 방법

dp[0][0]에 매우 작은 값을 할당하여 계산에 영향을 주지 않도록 처리함.

dp[0][0] = -987654321;

이렇게 하면 첫 번째 원소부터 올바르게 DP 점화식을 적용할 수 있음. 🎯

---

💻 최종 코드

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

public class Main {
    private static StringTokenizer st;
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static int N;
    private static int[] arr;
    private static int[][] dp;

    public static void main(String[] args) throws IOException {
        inputSetting();
        System.out.println(getAnswer());
    }

    private static int getAnswer() {
        int answer = Integer.MIN_VALUE;
        dp[0][0] = -987654321; // 초기화 필수!
        for (int i = 1; i <= N; i++) {
            dp[i][0] = Math.max(dp[i - 1][0] + arr[i], arr[i]);
            dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1] + arr[i]);
            answer = Math.max(answer, Math.max(dp[i][0], dp[i][1]));
        }
        return answer;
    }

    private static void inputSetting() throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        dp = new int[N + 1][2];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    }
}

---

🎯 마무리: 이 문제에서 배운 점!

✔ 누적합 방식의 한계 🚫

• 연속 구간의 합 계산에는 유용하지만, 한 개의 원소 제거 조건을 효율적으로 반영하기 어려움.

✔ DP 접근의 장점 ✅

• 두 가지 상태(제거 전/후)를 관리하면 한 원소 제거 조건을 O(n)으로 해결 가능!

✔ 초기화의 중요성 💡

• dp[0][0]을 올바르게 초기화하지 않으면 이후 계산이 꼬일 수 있음.

---