[DP] 백준 1912 연속합 (Continuous Sum)

BackJoon 

#1912 - 연속합 (Continuous Sum)

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

대표적인 DP문제입니다.

DP[N] 을 N개 자리수에 연속합을 한 것들 중에서 가장 큰 연속합 이라고 하겠습니다.

N자리에 해당하는 숫자가 이전 연속합에 속하는 경우와 속하지 않고 새롭게 연속합을 시작하는 경우 2가지로 나누어서 생각해 볼 수 있습니다.

ARR 배열은 주어진 수열을 담고 있습니다.

N자리에 숫자를 연속합에 합치면, 이득인 경우

DP[N] = DP[N-1] + ARR[N] 

N자리에 숫자를 연속합에 합치면, 이득을 얻지 못하는 경우 (새롭게 다시 연속합을 시작해야함)

DP[N] = ARR[N] 

그렇다면 이 2가지 경우를 분기 처리해야 하는데 어떻게 할까요???

우선 N자리 값과 N-1까지 연속한 합을 합친 값과 N자리의 값을 비교해서 더 큰 값을 도출하는 경우로 분기처리 하면 됩니다. 아래 코드에 나와 있으니 쉽게 이해가 가실거라 생각합니다.

이제 위 점화식 컨셉을 코드로 옮겨보면 다음과 같습니다.

package BackJoon;

import java.util.Arrays;
import java.util.Scanner;

public class ContinuousSum {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] dp = new int[n+1];
		int[] arr = new int[n+1];

		for (int i = 1; i <= n; i++) {
			arr[i] = sc.nextInt();
		}

		dp[1] = arr[1];
		int max = dp[1];
		for (int i = 2; i <= n; i++) {
			//이전 연속합과 자신의 값을 합한 값과 자기 자신을 포함하지 않고 새롭게 시작하는 값인 자신의 값 중 크기에 따라
			//분기 처리
			if (dp[i-1] + arr[i] > arr[i]) {
				//포함하는 경우
				dp[i] = dp[i-1] + arr[i];
			} else {
				//새롭게 합을 시작하는 경우
				dp[i] = arr[i];
			}

			max = Math.max(max, dp[i]);
		}
		System.out.println(Arrays.toString(dp));
		System.out.println(max);

	}

}