[백준 *Java] - 연속합2 (11398)

 

연속합 2 문제보기

13398번: 연속합 2

문제 설명
n개의 정수로 이루어진 임의의 수열이 주어진다.
우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합중 가장 큰 합을 구하려고 한다.
단, 수는 한개 이상 선택해야 한다.
또 수열에서 수를 하나 제거할 수 있다.(제거하지 않아도 된다.)
예를 들어,
10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자.
여기서 수를 제거하지 않았을 때의 정답은 12 + 21인 33이 정답이 된다.
만약,
-35를 제거 한다면 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1 이 되고,
여기서 정답은 10-4+3+1+5+6+12+21 인 54가 된다.

입력
첫째 줄에 정수 n(1 <= n <= 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다.
수는 -1,000 보다 크거나 같고, 1,000 보다 작거나 같은 정수이다.

출력
첫째 줄에 답을 출력한다.

---

👇 접근방식 (내 생각정리)

연속합이라는 문제를 푼 상태라, 거기서 조건 한 가지가 추가된 상태라 생각했습니다.
가장 먼저 생각이 든 건, 2차원 배열을 이용해서

idx '0' 쪽에는 기존에 연속된 DP 합 값을 넣어놓고, idx '1' 에는 수열에서 수를 제거한 값을 저장을 할 생각이였습니다.

하지만,

점화식이 정리가 되지 않고 더 복잡해지면서 경우의 수가 늘어나는 거 같아 이 방법이 아니라 생각했습니다..

오늘은 머리가 잘 굴러가지가 않네요 :(

다른 분들 코드를 참고하겠습니다.

---

풀이 방법은 2가지 방식이 있습니다.

DP배열을 1차원으로 하냐? 2차원으로 하냐의 차이로 풀이방법이 달라집니다. 

아래에 하나씩 풀이방법을 다르게 설명하겠습니다.

 

먼저

1차원 배열로 푼 방법입니다.

DP배열을 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 연속합을 구하듯 DP배열에 부분 문제를 해결한 값을 저장합니다.

연속합(1912) 문제보기

위에는 연속합 문제 풀이내용입니다. 혹시, 연속합 문제를 풀지 않았다면, 한 번 풀어보고 블로그 내용을 확인하고 오세요.

인덱스 번호 ->	0	1	2	3	4	5	6	7	8	9
예제1 테스트케이스	10	-4	3	1	5	6	-35	12	21	-1
DP1 저장된 값(왼쪽에서 오른쪽) -------->	10	6	9	10	15	21	-14	12	33	32
DP2 저장된 값(오른쪽에서 왼쪽) <--------	21	11	15	12	11	6	-2	33	21	-1
DP = DP1 + DP2 DP[i] = DP1[i-1] + DP2[i+1]		25	18	20	16	13	54	7	11

위 테이블 표는 설명을 하기 쉽게, 표로 적어 놓은 것입니다.

결국, 배열의 값 중 하나를 뺄수도 있고? 빼지 않을 수도 있습니다.

일단 위의 도표는 뺀다는 걸 가정하에, 모든 배열에서 하나의 값을 뺀 수열의 연속된 합을 나타냅니다.

그 수 하나를 뺀 최대합과 수에서 빼지않고 연속된 수의 최대 합과 비교를 하여,

수를 뺀값이 더 큰지? 빼지않을 때가 더 큰지 비교를 해주면 됩니다.

 

위에 설명한대로 코드를 작성해보겠습니다.

주석을 확인하면 더 이해하기 쉽습니다.

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

public class Main {
    static int [] dpLeftToRight;
    static int [] dpRightToLeft;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        dpLeftToRight = new int[N+1];
        dpRightToLeft = new int[N+1];
        int [] arr = new int[N+1];

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

		// 초기화를 합니다. 
        dpLeftToRight[0] = arr[0];
        dpRightToLeft[N-1] = arr[N-1];

        // 왼쪽에서 오른쪽 방향으로
        int max = arr[0];
        for (int i = 1; i < N; i++) { // 0은 초기화가 되어있음.
            dpLeftToRight[i] = Math.max(arr[i], dpLeftToRight[i-1] + arr[i]);
            max = Math.max(max, dpLeftToRight[i]);
        }
        // 오른쪽에서 왼쪽방향으로
        for (int i = N-2; i >= 0; i--) { // N-1은 초기화가 되어있음.
            dpRightToLeft[i] = Math.max(arr[i], dpRightToLeft[i+1] + arr[i]);
            // 여기서는 굳이 max 세팅을 하지 않아도 됩니다.
        }

        for (int i = 1; i < N-1; i++) { // 1부터 N-1까지입니다 why? i-1,i+1일때, 0일 때, 인덱스-1을 조회를 하고 N일 때, 인덱스 N+1을 조회해서, ArrayIndexOutOfBoundsException 에러 발생합니다.
            int excludeNum = dpLeftToRight[i-1] + dpRightToLeft[i+1];// 이렇게 하면 수 i인, 1개를 제외한 수열의 최대 합을 찾을 수 있습니다.

            max = Math.max(max, excludeNum);
        }
        System.out.println(max);
    }
}

---

 

다음은

2차원 배열로 푼 방법입니다.

2차원 배열로 풀 때는, 

DP[N][K] 일때,

N은 수열 인덱스라고 생각하면됩니다.

K는 0과 1만 존재하고, 0은 제거할 경우 / 1은 제거하지 않을 경우로 나눕니다.

 

K가 0일 경우, DP[N][0]는 제거하는 수가 없으니, 연속합의 문제처럼 생각하시면 됩니다.

K가 1일 경우, DP[N][1]는 2가지 경우를 더 생각해야합니다.

1. 특정 수를 처음 제거하는 경우 --> DP[N][1] = DP[N-1][0]

2. 특정 수 이전에 제거된 수가 있을 경우 --> DP[N-1][1] + arr[i] vs DP[N-1][0]

이렇게 두 가지로 나뉘는데,

2번 같은 경우에는 제거 된 수가 있기 때문에 또 다시 다른 수를 제거할 수 없습니다.

그렇게 되면, 비교를 해주어야합니다.

현재 N루프 일때,

그 N을 제거할 것인가?  DP[N-1][0] 와,

먼저 제거된 수를 가지고 현재 N루프를 더 할 경우. DP[N-1][1] + arr[i]

를 비교해주어야합니다.

그러면, DP[N][1] = Math.max(DP[N-1][0], DP[N-1][1]. + arr[N] 

이렇게 나올 것입니다.

테이블 표로 설명을 먼저 하겠습니다.

인덱스번호	0	1	2	3	4	5	6	7	8	9
테스트 케이스	10	-4	3	1	5	6	-35	12	21	-1
DP[N][0] 저장	10	10	9	10	15	21	-14	12	33	32
DP[N[1] 저장	10	10	13	14	19	25	21	33	54	53
MAX 값 변화		10	13	14	19	25	21	33	54	53

 

코드 구현을 한뒤, 주석을 통해서 정리해보겠습니다.

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

public class Main {
    static int [][] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int [] arr = new int[N+1];
        DP = new int[N+1][2];

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

        // 초기화, 0번째는 그 수 입니다.
        DP[0][0] = arr[0];
        DP[0][1] = arr[0];

        int max = arr[0];
        for (int i = 1; i < N; i++) {
            // 기존 연속합 최대를 구하는 점화식입니다.
            DP[i][0] = Math.max(arr[i],DP[i-1][0] + arr[i]);

            // 수 i를 제거한 값과,
            // 이전에 제거된 수가 있는 경우, 이전 최대 연속합에 i번째 값을 더해줍니다.
            DP[i][1] = Math.max(DP[i-1][0], DP[i-1][1] + arr[i]);
            // 그리고, 0,1 에 있는 값을 비교 한뒤, max 값을 최신화 시켜줍니다.
            max = Math.max(max,Math.max(DP[i][0], DP[i][1]));

        }
        System.out.println(max);
    }
}