BOJ - 연속합2

leehyunjon·2022년 11월 11일

DP boj

Algorithm

목록 보기

125/162

연속합 13398 : https://www.acmicpc.net/problem/13398

Problem

Solve

부분 연속합이 최대가 되는 값을 찾아야하는 문제입니다.
이때, 연속되는 수 중 하나를 제거할수도 있기때문에 이를 해결하는것이 조금 까다롭습니다.

먼저 연속된 합을 저장해주는 dp를 선언해주어야합니다.
이때, dp는 특정 수가 삭제되지않은 경우와 삭제된 경우 두가지를 고려해야합니다.
그렇기 때문에 dp를 2차원 배열로 선언해줍니다.
dp[i][0]은 특정 수가 삭제되지 않은 경우, dp[i][1]은 특정 수가 삭제된 경우입니다.

먼저 특정 수가 삭제되지 않은 경우 이전 최대값 + 현재값과 현재값을 비교해서 큰 값을 갱신해줍니다.
점화식은 dp[i-1][0]+seq[i]가 되고 Math.max(do[dp-1][0]+seq[i],seq[i])로 dp[i][0]을 갱신해줍니다.

그 다음으로 특정값이 삭제된 경우 현재값을 삭제한경우와 이전 특정값을 삭제한 최대값을 비교해서 큰 값을 갱신해줍니다.
이때, 이전 특정값을 삭제한 최대값은 어떤 값이 삭제되었을 경우가 있기때문에 현재값을 더해주어야합니다.

현재값을 삭제한 경우의 점화식은 dp[i-1][0]
이전 특정값을 삭제한 최대값 경우의 점화식은 dp[i-1][1]+seq[i]

즉, Math.max(dp[i-1][0], dp[i-1][1]+seq[i])가 되게됩니다.

참조한 블로그에서는 두개의 1차원배열 dp를 이용해서 왼쪽에서부터 연속된 최대합과 오른쪽에서부터 연속된 최대합을 통해 해당 수를 제외하여 합을 구하는 방법도 있었습니다. (해당 풀이가 좀더 직관적이고 깔끔해보입니다.)

Code

import java.io.*;
import java.util.StringTokenizer;
public class Main{
	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 N = Integer.parseInt(br.readLine());
		int[] seq = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<N;i++){
			seq[i] = Integer.parseInt(st.nextToken());
		}

		int[][] dp = new int[N][2];
		dp[0][0] = seq[0];
		int answer = dp[0][0];
		for(int i=1;i<N;i++){
			dp[i][0] = Math.max(dp[i-1][0]+seq[i],seq[i]);
			dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1]+seq[i]);
			answer = Math.max(answer,Math.max(dp[i][0],dp[i][1]));
		}

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}
}