[백준 - 1912번] 연속합- JAVA 정리 및 해설

안녕하세요. 오늘 풀어 볼 문제는 연속합입니다. 연속합은 Dynamic Programming을 이용한 문제입니다. 

연속합은 연속된 수중에서 가장 큰 합을 구하는 문제이기 때문에 수열마다 연속적으로 수를 더해가면서 그합이 가장 큰 경우를 찾으면 된다고 생각해서 문제를 이런식으로 풀 수도 있습니다.

 

수열에서 n번째 수부터 마지막까지 연속적으로 더해가면서 가장 큰 수를 cache[n]에 저장하고 그 cache배열에서 가장 큰수를 더해가는 방식으로 문제를 풀었습니다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int cache[] = new int[1000005];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		int num[] = new int[n+1];
		Arrays.fill(cache, -1);
		String tc = br.readLine();
		StringTokenizer st = new StringTokenizer(tc," ");
		for(int i=1; i<n+1; i++){
			num[i] = Integer.parseInt(st.nextToken());
			cache[i] = num[i];
		}
		for(int i=1; i<n+1; i++){
			int temp = cache[i];
			for(int j=i+1; j<n+1; j++){
				temp+=num[j];
				cache[i] = Math.max(cache[i], temp);
			}
		}
		int max = Integer.MIN_VALUE;
		for(int i=1; i<n+1; i++){
			max = Math.max(cache[i], max);
		}
		wr.write(String.valueOf(max));
		wr.flush();
		wr.close();
	}

}

하지만 이렇게 문제를 풀면 시간 초과가 나게됩니다. 왜일까요?

지금 제 코드문은 For문이 두개 있기때문에 O(n^2)의 시간 복잡도를 가지게 됩니다.

이 문제는 n의 범위가 100,000 이하이기때문에 최대의 경우 10^10를 가지게 되므로. 10,000,000,000 => 100억번의 연산을 하게 될 가능성이 있습니다 .

즉, "100억"번의 연산을 하게된다면, 시간상으로는 100초 넘게 걸리는 것이고 이 문제의 시간 제한은 2초이하이기때문에 시간 초과가 나게 됩니다. 

 

그러면 적어도 O(N)이 되는 코드를 짜야하고, 여기에서는 한가지 생각 전환이 필요합니다. 모든 수를 다 더할 필요가 없다는것에 중점을 맞추는게 중요합니다. 

 

즉, " cache(임의로 잡은 숫자부터 N번째 수열의 수 전까지 합한 값) + 이전의 숫자까지 더한것) +  N번째 순열의 수 와 N번째 수열의 수의 크기를 비교하면 모든 수를 확인해보지 않고 연속된 합이 최대인 경우를 찾을 수 있을 것입니다.

 

1. cache(임의로 잡은 숫자부터 N번째 순열의 수 전까지 합한 값) + 이전의 숫자까지 더한것) +  N번째 순열의 수 > N번째 수열의 수

인경우

 

이때는 N까지 수열의 수 연속합을 포함하는 경우입니다. 이전 임의로 잡은 숫자부터 N까지 합이 연속합중에서 큰 수입니다. 물론, 연속합 중에서 가장 큰 수는 아닐지 몰라도 현재 상황에서는 연속합 중 큰 수입니다.

 

2. cache(임의로 잡은 숫자부터 N번째 수열의 수 전까지 합한 값) + 이전의 숫자까지 더한것) +  N번째 수열의 수 < N번째 수열의 수

인경우

 

이때는 N번째 수열 수의 전값까지 연속합이 작아지는 경우고 N번째 수열의 수부터 다시 새로운 연속합을 시작해버리면 됩니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int cache[] = new int[1000005];
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		int num[] = new int[n+1];
		Arrays.fill(cache, -1);
		String tc = br.readLine();
		StringTokenizer st = new StringTokenizer(tc," ");
		for(int i=1; i<n+1; i++){
			num[i] = Integer.parseInt(st.nextToken());
			cache[i] = num[i];
		}
        //cache(임의로 잡은 숫자부터 N번째 순열의 수 전까지 합한 값) + 이전의 숫자까지 더한것) +  N번째 순열의 수와 N번째 수열의 수를 비교하는 함수.
		for(int i=2; i<n+1; i++){
			cache[i] = Math.max(num[i], num[i]+cache[i-1]);
			
		}
		int max = Integer.MIN_VALUE;
        //연속합중에서 가장 큰 수를 찾는 것.
		for(int i=1; i<n+1; i++){
			max = Math.max(cache[i], max);
		}
		wr.write(String.valueOf(max));
		wr.flush();
		wr.close();
	}

}

이런식으로 풀게되면 문제를 해결 할 수 있습니다.