[백준_1912번] 연속합

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

1912번: 연속합

[문제]

 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1912 {
	public static int n;
	public static int[] num;
	public static Integer[] dp; 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		num=new int[n];
		dp=new Integer[n];
		
		for(int i=0;i<n;i++)
			num[i]=sc.nextInt();
		
		dp[0]=num[0];
		makesum(n-1); // dp의 마지막 인덱스 번호는 n-1이기 때문에 n-1을 매개변수로 호출
		
		/*
		 * dp에는 각 인덱스까지의 누적합 최대가 저장되어 있다.
		 * 저장되어 있는 누적합 중 최대를 찾아야 하기 때문에
		 * 아래와 같은 과정 수행
		 */ 
		int max=Integer.MIN_VALUE;
		for(int i=0;i<n;i++)
			max=(dp[i]>max)?dp[i]:max;
		
		System.out.println(max);
	}
	
	public static int makesum(int n) {
		if(dp[n]==null)
			/*
			 * (이전 인덱스 까지의 누적 합 + 현재 값)과 현재 값을 비교하여 최댓값을 저장
			 * 즉, dp[n]에는 인덱스 n까지의 최대 누적합이 저장되어 있다.
			 * 예를 들어 -10 2 3이 주어졌을 때 
			 * dp[2]는 (-10+2)와 2중 큰 값을 선택할 것이고
			 * dp[3]은 dp[2]+3(2+3) 또는 3중 큰 값을 선택할 것이다. 
			 */
			return dp[n]=Math.max(makesum(n-1)+num[n], num[n]);
		
		return dp[n];
	}
}

 

[고찰] 

 이번 문제의 함정은 무조건 연속된 양수들만 더한 누적 값이 최댓 값이 아니라는 것이다. 따라서 그리디 알고리즘이 아닌 각 인덱스마다 해당 인덱스까지의 누적 합을 더해서 dp에 저장해주는 동적 계획법을 사용해야 한다. 이를 알고 비교 대상을 잘 설정할 수 있다면 어렵지 않게 해결할 수 있는 문제였다.