[백준 13398번] 연속합 2 (java)

13398번: 연속합 2

백준 1912번 : 연속합 문제에서 좀 더 발전한 문제이다.

이번에는 주어진 수열에서 연속합을 구하되, 중간에 수 하나를 제거할 수가 있다.

 

백준 1912번 문제에서는 dp 1차원 배열을 이용하여 문제를 풀었는데, 이번에는 2차원 배열로 만들어서 풀었다. 아래는 백준 1912번 문제 풀이한 링크이다.

lotuslee.tistory.com/89

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

 

dp배열을 2차원 배열로 만들어서 수 하나를 제거했을 때의 연속합과, 제거하지 않았을 때의 연속합을

분리하였다.

int[][] dp = new int[n][2];

 

• dp[n][0] : n번째 수가 연속합의 마지막이면서, 수 하나를 제거했을 때의 연속합 중 최대값

• dp[n][1] : n번째 수가 연속합의 마지막이면서, 수를 제거하지 않았을 때의 연속합 중 최대값

입력받은 수열이 10 -4 3 1 5 6 -35 12 21 -1이고, 이 수열을 arr 1차원 배열에 저장했을 때,

 

dp[0][0] = 0, dp[0][1] = 10

dp[0][0]는 0번째 수(arr[0])를 마지막으로 포함하는 연속합 중에서 수 하나가 제거된 상태를 의미한다.

이 때, 0번째 수보다 앞에 있는 수는 없으므로 0번째 수(arr[0])를 포함하는 연속합은 arr[0] 자체이다.

그런데 여기서 수 하나가 제거된 상태라면, 제거할 수는 arr[0]뿐이므로 arr[0] - arr[0] = 0 이다.

dp[0][1]는 0번째 수(arr[0])를 마지막으로 포함하는 연속합 중에서 제거된 수가 없는 경우이다.

그러므로 dp[0][1] = arr[0] = 10 이 된다.

 

dp[1][0] = 10, dp[1][1] = 6

dp[1][0]는 1번째 수(arr[1])를 마지막으로 포함하는 연속합 중에서 수 하나가 제거된 상태를 의미한다.

1번째 수(arr[1])를 마지막으로 포함하는 연속합 중에서 수 하나가 제거된 경우는 두 가지가 있다.

 

[0번째 수가 제거된 경우]

만약 0번째 수를 제거했다면, 1번째 수는 제거하면 안된다. 전체 수열 중에서 수 하나만 제거가 가능하기 때문이다. 0번째 수를 제거했을 때의 최대값은 dp[0][0]이었다. 여기서 1번째 수(arr[1])를 더해야 하므로

dp[0][0] + arr[1] 이다.

 

[1번째 수가 제거된 경우]

1번째 수를 제거하는 경우라면 0번째 수는 제거되지 않은 상태일 것이다. 0번째 수를 제거하지 않았을 때의 최대값은 dp[0][1]이었다. 여기서는 1번째 수가 제거된 경우이므로 방금처럼 arr[1]를 더하면 안된다.

dp[0][1]

 

이렇게 두 가지 경우 중에서 연속합이 최대인 경우는 dp[0][0] + arr[1] = 0 + (-4) = -4, dp[0][1] = 10 중에서 dp[0][1] = 10 이다.

그러므로 dp[1][0]에는 dp[0][1]이 들어간다.

 

 

dp[1][1]는 1번째 수(arr[1])를 마지막으로 포함하는 연속합 중에서 제거된 수가 없는 경우이다.

1번째 수를 포함하는 연속합은 두 가지 경우가 있다.

• 0번째 수와 1번째 수를 모두 더하는 경우 -> dp[0][1] + arr[1]

• 1번째 수만 더하는 경우 -> arr[1]

이 중에서 최대가 되는 연속합은 dp[0][1] + arr[1] = 6이므로 dp[1][1]에는 6이 들어간다.

 

위의 예시를 바탕으로 점화식을 세우면 아래와 같다.

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

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

 

모든 dp 배열의 원소를 다 구한 후, 가장 큰 값이 연속합의 최대값이 된다.

 

소스코드 : 

	import java.io.*;
	import java.util.Arrays;
	public class n13398 {
	static int n;
	static int[] arr;
	static int[][] 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][2];
	String[] sarr = br.readLine().split(" ");
	for (int i = 0; i < n; i++)
	arr[i] = Integer.parseInt(sarr[i]);
	dp[0][0] = 0;
	dp[0][1] = arr[0];
	int max = dp[0][1];
	for (int i = 1; i < n; i++) {
	dp[i][0] = Math.max(dp[i - 1][0] + arr[i], dp[i - 1][1]);
	dp[i][1] = Math.max(dp[i - 1][1] + arr[i], arr[i]);
	max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
	}
	bw.write(max + "\n");
	bw.flush();
	}
	}

view raw 13398.java hosted with ❤ by GitHub