[BaekJoon] 13398 연속합 2 (Java)

1.  문제 링크

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

2.  문제

요약

• n개의 정수로 이루어진 수열에서 연속된 몇 개의 수를 선택해 구할 수 있는 합 중 가장 큰 합을 구하려고 합니다.
• 수는 한 개 이상 선택해야 하고, 수열에서 수를 하나 제거할 수 있습니다. 수는 제거하지 않아도 됩니다.
• n개의 정수로 이루어진 수열이 주어졌을 때, 수열에서 수를 한 개 제거하거나 제거하지 않고 구할 수 있는 합 중 가장 큰 합을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 n이 주어지고 두 번째 줄에 -1,000보다 크거나 같고 1,000보다 작거나 같은 정수인 n개의 정수로 이루어진 수열이 주어집니다.
• 출력: 첫 번째 줄에 구할 수 있는 합 중 가장 큰 합을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public int getMaxSum(int[] nums) {
		int[][] dp = new int[nums.length][2];
		dp[0][0] = nums[0];
		dp[0][1] = nums[0];
		int max = nums[0];
		for(int i = 1; i < nums.length; i++) {
			dp[i][0] = Math.max(dp[i - 1][0] + nums[i], nums[i]);
			dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1] + nums[i]);
			max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
		}
		return max;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		int[] nums = new int[num];
		String[] input = br.readLine().split(" ");
		br.close();
		for(int i = 0; i < num; i++) {
			nums[i] = Integer.parseInt(input[i]);
		}
		Main m = new Main();
		bw.write(m.getMaxSum(nums) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
• 2차원 배열 dp를 만드는데, 행은 주어진 각 수들까지의 최대 합을 나타냅니다.
• 열에서 index 0은 수를 제거하지 않는 경우를 뜻하고, index 1은 수를 하나 제거하는 경우를 뜻합니다.
• index 0일 때에는, 현재 수가 이전까지의 수를 더해온 값과 현재 수를 더한 값보다 크다면 현재 수부터 다시 더해나가는 것이 더 큰 수를 만들 수 있는 방법이기 때문에 현재 수를 dp 배열에 넣고 그렇지 않다면 이전까지의 수를 더해온 값과 현재 수를 더한 값을 dp 배열에 넣습니다.
• index 1일 때에는 두 가지 경우가 일어날 수 있습니다.
  • 현재 수를 제거하려는데 이전까지 제거한 수가 없다면 이전까지의 최대 합을 그대로 현재 dp 값으로 취합니다.
  • 현재 수를 제거하려는데 이전에 제거한 수가 이미 존재한다면 현재 수를 제거할 수 없으므로 이전까지의 최대 합에 현재 수를 더한 값을 현재 dp 값으로 취합니다.
• 위와 같은 규칙으로 dp를 채워나가며 현재 값에서 index 0인 경우의 값과 index 1인 경우의 값 중 더 큰 값을 최대 합으로 취하고 마지막까지 dp를 채운 후에 최대 합으로 남아있는 수가 이 문제의 답이 됩니다.
• 위 규칙을 점화식으로 나타내면 아래와 같이 나타낼 수 있습니다.
  • 배열 nums에 주어진 수들이 들어있는 경우, i번째 수에서의 최대 합 구하기
  • index가 0일 때
    • dp[i][0] = Math.max(dp[i - 1][0] + nums[i], nums[i])
  • index가 1일 때
    • dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1] + nums[i])
• 위 점화식을 바탕으로 구할 수 있는 합 중 가장 큰 합을 구합니다.

1. 주어진 수들을 배열 nums에 담습니다.
2. 주어진 각 수들까지의 최대 합을 나타내기 위한 2차원 배열 dp를 생성하고 첫 번째 행의 값들은 nums의 첫 번째 값으로 초기화합니다.
3. 주어진 수들에서 구할 수 있는 최대 합을 나타내는 변수인 max를 생성하고 nums의 첫 번째 값으로 값을 초기화합니다.
4. nums의 두 번째 값부터 마지막 값까지 반복문을 돌면서 구할 수 있는 최대 합을 구합니다.
   1. 위에서 구한 점화식을 바탕으로 수를 제거하는 경우와 수를 제거하지 않은 경우에 대한 최대 합을 구합니다.
   2. 두 경우 중 더 큰 값을 max의 값으로 취합니다.
5. 4번의 반복문이 끝난 후의 max 값을 출력합니다.