[백준] 1912번: 연속합(DP)

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

1912번: 연속합

코드

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

public class Main {

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

}

풀이

위 문제를 완전 탐색으로도 풀 수 있다.

수열에서 n번째 수 부터 마지막까지 연속적으로 더해가며 비교해서 더 큰 수를 저장하는 방식으로 해결하면,

2중 for문으로 해결해야 하는데, 문제에서 n의 범위는 100,000 까지다

따라서 O(100,100 * 100,100) 을하면 100억이 나와 시간초과가 발생한다.

따라서 DP 문제라는것에 초점을 맞춰 해결했다.

 

dp[i] = i개 자리수의 연속합을 한 것들 중 가장 큰 연속합이라고 했을때,

경우의수는 다음 2가지가 있다.

1) i자리에 해당하는 숫자가 이전 연속합에 속하는 경우 

2) 속하지 않고 새롭게 연속합을 시작하는 경우

 

1)의 경우 dp[i] = dp[i-1] + arr[i] 이고,

2)의 경우 dp[i] = arr[i] 이다.

 

즉, 2)의 뜻은 이전까지의 합이 음수면 새로 더하는 값은 무조건 현재보다 작다인데,

만약 [-1, 2, -4, 10] 의 경우 dp[3]을 구해보자.

 

1) dp[3] = dp[2] + arr[3] 

2) dp[3] = arr[3] 

위 두 경우가 있다.

하지만 첫번째 경우, 음수가 나오므로 무조건 arr[3]보다 작기 때문에 10부터 새롭게 연속합을 시작해야 한다.