[백준 13398] 연속합 2 (자바)

 

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

13398번: 연속합 2

 

난이도 : 골드 5

 

제일 자신 없는 다이나믹 프로그래밍입니다.

많이 풀다 보니 조금은 풀이가 보이네요.

 

연속된 수를 선택하여 가장 큰 합을 구하는 문제입니다. 

단, 연속된 수에서 1개의 수를 제거할 수 있습니다.

저는 2차원 배열로 제거를 안 한 경우, 제거를 한 경우의 최댓값을 구했습니다.

 

 

0은 수를 제거하지 않은 경우의 최대값, 1은 수를 제거한 경우(제거 안 한 경우 포함)의 최댓값입니다.

0번째 줄의 점화식은 dp[i][0] = Math.max(dp[i-1][0]+array[i], array[i]) 입니다.

자기 자신이 꼭 식에 들어가야 하므로 이전까지의 최댓값과 자기 자신의 합, 자기 자신 중에서 최댓값을 가져오면 됩니다.

 

1번째 줄의 점화식은 dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]+array[i]) 입니다.

자기 자신을 제거해야 할 경우와 제거 안 해도 될 경우가 있습니다.

 

자기 자신을 제거해야 할 경우 지금까지 수를 제거한 적이 없어야 합니다. 

따라서 i-1의 0번째 행의 값을 가져옵니다.

자기 자신을 제거하지 않아도 될 경우에서는 i-1의 1번째 행과 자기 자신을 더해줍니다.

n번째의 1번째 행은 0번째 행보다 무조건 크거나 같습니다.

필요한 경우 숫자 1개를 지워서 최적화 해왔기 때문입니다.

---

메소드

void main 

입력을 받고 dp에 값을 구합니다.

 

import java.util.*;
import java.io.*;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer stz = new StringTokenizer(br.readLine());
		int array[] = new int[n];
		int dp[][] = new int[n][2];

		for(int i = 0; i < n; i++)
			array[i] = Integer.parseInt(stz.nextToken());

		int max = array[0];
		dp[0][0] = array[0];
		dp[0][1] = array[0];

		for(int i = 1; i < n; i++) {
			dp[i][0] = Math.max(dp[i-1][0] + array[i], array[i]);
			dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]+array[i]);
			max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
		}

		System.out.println(max);
	}

}

 

 

다이나믹 프로그래밍 문제는 코드가 짧습니다.

코드가 짧은만큼 못 풀었을 때 더 슬퍼요.

파이팅입니다.