[백준 알고리즘] 1912 연속합(with Java)

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

주어진 수열에서 연속된 숫자의 가장 큰합을 구하는 문제이다.

가장 직관적인 방법으로 모든 케이스를 돌려보는 방법이 있다.

10, -4, 3, 1, 5, 6, -35, 12, 21, -1

이와 같은 수열일 경우

10 = 10

10 + -4 = 6

10 + -4 + 3 = 9

.....

-4 + 3 = -1

-4 + 3 + 1 = 0

....

-1

이런식으로 모든 경우의 수를 만들어서 다 돌려보는 것이다.

import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); ArrayList<Integer> numbers = new ArrayList<Integer>(); for(int i = 0; i < n; i++) { numbers.add(sc.nextInt()); } // System.out.println(solve1(n, numbers)); System.out.println(solve2(n, numbers)); } public static int solve1(int n, ArrayList<Integer> numbers) { int sum = 0; int maxSum = Integer.MIN_VALUE; for(int i = 0; i < n; i++) { sum = numbers.get(i); for(int j = i+1; j < n; j++) { sum = sum + numbers.get(j); if(sum > maxSum) { maxSum = sum; } } } return maxSum; } public static int solve2(int n, ArrayList<Integer> numbers) { int sum = 0; int maxSum = Integer.MIN_VALUE; ArrayList<Integer> temp = new ArrayList<Integer>(); for(int i = 0; i < n; i++) { int a; if(i < 1) { a = 0; }else { a = temp.get(i-1); } int b = numbers.get(i); if(a+b > b) { temp.add(a+b); }else { temp.add(b); } if(maxSum < temp.get(i)) { maxSum = temp.get(i); } } return maxSum; } }

위의 소스에서 solve1() 메소드는 앞에서 설명한 것과 같이

모든 케이스를 다 만들어서 계산하도록 구현한 것이다.

하지만 결과는 시간 초과!

고민고민 끝에 solve2() 메소드를 새로 만들었다.

방법은 

DP(Dynamic Programming, 동적계획법)!

현재 index의 숫자와

지난 index까지의 최대합을 계속해서 비교해 나가는 방식이다.

	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
numbers	10	-4	3	1	5	6	-35	12	21	-1
temp	10	6	9	10	15	21	-14	12	33	32

위 표에서 

temp[0] = max(0, number[0])

temp[1] = max(temp[0] + number[1], number[1])

temp[2] = max(temp[1] + number[2], number[2])

temp[3] = max(temp[2] + number[3], number[3])

......

이렇게 하면 모든 경우의 수를 일일이 계산하지 않아도

연속합의 최대값을 구할 수 있다.