[백준/JAVA] 13398번: 연속합 2

🔺 문제

13398번: 연속합 2

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());
        
        // A 배열 저장하기
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] A = new int[N];
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        // L 배열 채우기 (왼쪽 → 오른쪽으로 idx를 포함한 최대 연속 합)
        int[] L = new int[N];
        L[0] = A[0];
        int result = L[0];
        for(int i = 1 ; i < N ; i++) {
            L[i] = Math.max(A[i], L[i - 1] + A[i]);
            result = Math.max(result, L[i]);    // 기본 최댓값 : 1개도 제거하지 않을 때
        }
        
        // R 배열 채우기 (오른쪽 → 왼쪽으로 idx를 포함한 최대 연속 합)
        int[] R = new int[N];
        R[N - 1] = A[N - 1];
        for(int i = N - 2 ; i >= 0 ; i--) {
            R[i] = Math.max(A[i], R[i + 1] + A[i]);
        }
        
        // 🔔 L[i-1] + R[i+1] : i번째 값을 제거한 효과
        for(int i = 1 ; i < N - 1 ; i++) {
            result = Math.max(result, L[i - 1] + R[i + 1]);
        }
        
        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

✅ 해결 아이디어
✔ DP - 점화식
- 배열 L : 왼쪽 → 오른쪽으로 idx를 포함한 최대 연속 합
- 배열 R : 오른쪽 → 왼쪽으로 idx를 포함한 최대 연속 합
- L[ i - 1 ] + R[ i + 1 ] : i번째 값을 제거한 효과

---

🔺 다른 풀이들

- 1차원 배열 풀이, 2차원 배열 풀이 둘 다 올려주심

[BOJ] 백준 13398번 : 연속합 2 (JAVA)

 

 

- 2차원 배열 과정 설명 굿

[백준 13398번] 연속합 2 (java)

---

💬 느낀 점

DP야.. 우리 언제쯤 친해지니..?

 

 

1회독	2회독	3회독	4회독	5회독
V	7/6

---

(참고)

✔ Do it 알고리즘 코딩테스트 자바편