[백준 1912번] 연속합 (java)

1912번: 연속합

 

다이나믹 프로그래밍으로 풀었다.

다이나믹 프로그래밍은 무엇보다 점화식을 세우는 것이 중요하다.

나는 int[] dp = new int[n]; 로 1차원 dp배열을 생성하였고, dp[n]의 의미는 다음과 같이하였다.

 

• dp[n] : n번째 수가 연속합의 마지막일 때, 최대가 되는 연속합

무슨 말이냐면, 입력받은 수열을 배열 arr에 저장한다고 했을 때,

 

arr[0] + ... + arr[n] : 0번째 수부터 n번째 수까지의 연속합

arr[1] + ... + arr[n] : 1번째 수부터 n번째 수까지의 연속합

arr[2] + ... + arr[n] : 2번째 수부터 n번째 수까지의 연속합

.

.

.

arr[n-1] + arr[n] : n-1번째 수부터 n번째 수까지의 연속합

arr[n] : n번째 수부터 n번째 수까지의 연속합

 

중에서 비교하여 가장 큰 연속합이 dp[n]에 들어가는 것이다. 

 

마지막에 arr[n]도 비교하는 이유는 연속합이 꼭 0번째 수부터 시작하지 않으며, 수열의 중간에서부터 더한 연속합이 최대가 될 수도 있기 때문이다.

 

즉, dp[n]에 대한 점화식을 세우면 다음과 같다.

dp[n] = Math.max(dp[n-1] + arr[n], arr[n])

dp[n-1]는 n-1번째 수가 연속합의 마지막일 때 최대가 되는 연속합이다.

이 연속합에서 n번째 수(arr[n])를 더한 결과 dp[n-1] + arr[n] 와 n번째 수(arr[n])를 비교하여 더 큰 값을 dp[n]에 넣는다.

예를 들어, 임의의 수열 -1 -1 -1 -1 5 가 주어지고 n = 4 일 때,

dp[n-1] = dp[3] = -1 이다.

dp[3] + arr[4] = -1 + 5 = 4 이지만, arr[4] = 5 이므로 dp[3] + arr[4] < arr[4] 이 되어서 dp[4]에는 5가 들어간다. 여기서 dp[n-1]가 음수라면 dp[n-1] + arr[n] 보다 arr[n]가 더 크다는 사실을 알 수 있다. 

 

dp[0]부터 dp[n-1]까지 모두 구하고 난 후, 이들 중 가장 큰 값이 연속합의 최대값이 된다.

 

위의 점화식을 사용하면 문제를 쉽게 풀 수 있다.

아래는 그 소스코드이다.

 

소스코드 : 

	import java.io.*;
	import java.util.Arrays;
	public class n01912 {
	static int n;
	static int[] arr, dp;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	n = Integer.parseInt(br.readLine());
	arr = new int[n];
	dp = new int[n];
	String[] input = br.readLine().split(" ");
	for (int i = 0; i < n; i++)
	arr[i] = Integer.parseInt(input[i]);
	dp[0] = arr[0];
	for (int i = 1; i < n; i++) {
	dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
	}
	Arrays.sort(dp);
	bw.write(dp[n - 1] + "\n");
	bw.flush();
	}
	}

view raw 1912.java hosted with ❤ by GitHub