백준 13398번: 연속합 2

문제

https://www.acmicpc.net/problem/13398

13398번: 연속합 2

---

풀이

n개의 정수로 이루어진 수열 중에서 수열에서 수를 하나 제거할 수 있을 때 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제입니다.

---

코드

자바

탑다운 방식을 이용한 코드입니다.

dp1 배열은 임의의 수 x가 있을 때 arr[x]가 맨 오른쪽에 있을 때 수열에서 수를 하나 제거하지 않고 연속된 몇 개의 수의 합 중 가장 큰 값을 의미합니다.

continous 함수 안에서 dp1[idx]가 null이라면 coninous(idx - 1)를 재귀적으로 실행하여 dp1[idx - 1]를 받아 그 값에 arr[idx]값을 더한 값과 아무것도 더하지 않은 arr[idx]값을 비교해서 더 큰 값을 넣습니다.

이후 max값과 dp[idx]값을 비교해가며 최댓값을 구하기 때문에 모든 입력이 끝난 후에 continous(n - 1)을 실행하여 dp1[n - 1부터 0]을 모두 비교한 뒤에 수열에서 수를 하나 제거하지 않았을 때의 max를 구한 후에 continous2 함수를 실행합니다.

dp2 배열은 임의의 수 x가 있을 때 arr[x]가 맨 왼쪽에 있을 때 수열에서 수를 하나 제거하지 않고 연속된 몇 개의 수의 합 중 가장 큰 값을 의미합니다.

continous2 함수 안에서 dp2[idx]가 null이라면 coninous2(idx + 1)를 재귀적으로 실행하여 dp2[idx + 1]를 받아 그 값에 arr[idx]값을 더한 값과 아무것도 더하지 않은 arr[idx]값을 비교해서 더 큰 값을 넣습니다.

이후 i를 포함한 for문 안에서 dp1[i - 1] + dp2[i + 1]와 max값을 비교해가며 수열에서 arr[i]를 제거했을 때 최댓값을 구한 후에 출력합니다.

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

public class Main {

    static int max = Integer.MIN_VALUE;
    static int[] arr;
    static Integer[] dp1, dp2;

    public static int continous(int idx) {
        if (dp1[idx] == null) {
            dp1[idx] = Math.max(continous(idx - 1) + arr[idx], arr[idx]);
        }
        max = Math.max(max, dp1[idx]);
        return dp1[idx];
    }

    public static int continous2(int idx) {
        if (dp2[idx] == null) {
            dp2[idx] = Math.max(continous2(idx + 1) + arr[idx], arr[idx]);
        }
        return dp2[idx];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        dp1 = new Integer[n];
        dp2 = new Integer[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dp1[0] = arr[0];
        continous(n - 1);
        dp2[n - 1] = arr[n - 1];
        continous2(0);
        for (int i = 1; i < n - 1; i++) {
            max = Math.max(max, dp1[i - 1] + dp2[i + 1]);
        }
        System.out.println(max);
    }
}

C언어

바텀업 방식을 이용한 코드입니다.

dp1 배열과 dp2 배열은 탑다운 방식의 코드에서의 의미와 동일하며 모든 입력이 끝나면 i가 1부터 시작하는 for문으로 들어가고 dp1 배열을 채워가며 수열에서 수를 하나 제거하지 않았을 때의 max를 구합니다.

이후 i가 n - 2부터 시작하는 for문으로 들어가서 dp2 배열을 동일한 방식으로 채운 뒤에 마지막 i를 포함한 for문 안에서 dp1[i - 1] + dp2[i + 1]와 max값을 비교해가며 수열에서 arr[i]를 제거했을 때 최댓값을 구한 후에 출력합니다.

#include <stdio.h>
#include <stdlib.h>
#define math_max(a, b) a > b ? a : b
main() {
	int n;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	int* dp1 = (int*)malloc(sizeof(int) * n);
	int* dp2 = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	int max = dp1[0] = arr[0];
	for (int i = 1; i < n; i++) {
		dp1[i] = math_max(dp1[i - 1] + arr[i], arr[i]);
		max = math_max(max, dp1[i]);
	}
	dp2[n - 1] = arr[n - 1];
	for (int i = n - 2; i >= 0; i--) {
		dp2[i] = math_max(dp2[i + 1] + arr[i], arr[i]);
	}
	for (int i = 1; i < n - 1; i++) {
		max = math_max(max, dp1[i - 1] + dp2[i + 1]);
	}
	printf("%d", max);
}

 

---

결론

연속합 문제에서 자바로 탑다운 방식을 이용한 코드에서 다이나믹 프로그래밍이 필요하지 않다고 느껴져서 찝찝했었는데 이 문제에서 잘 활용했던 것 같습니다.