[백준] 13398번 연속합 2 [Java]

DP문제이고, 누적합을 활용해서 푸는 문제이다.

다만 중간에 값을 "하나"를 제거할 수 있다.

그리고 "하나"의 값을 무조건 선택해야 된다.

이 조건을 생각하지 않고 풀어서 첫번째 제출에서는 틀렸다...

 

👨‍🏫 풀이

0 : 제거하지 않은 경우 , 1: 제거한 경우

현재 인덱스에서 값을 제거한 경우와 제거하지 않은 경우를 나눠서 풀면된다.

현재 인덱스 기준으로 값을 하나도 제거하지 않은 경우

• 이전 인덱스에서 값을 제거하지 않은 경우 + 현재 인덱스 값  : dp[i-1][0] + nums[i]
• 현재 값: nums[i]

두 값중 큰 것을 취하면 된다.

현재 인덱스 기준으로 제거한 값을 제거한 경우

• 이전 인덱스에서 값을 제거한 경우 + 현재 인덱스 값: dp[i-1][1] + nums[i]
• 현재 값을 제거한 경우: dp[i-1][0]

두 값중 큰 것을 취하면 된다.

 

이전  까지의 값들 중 가장 큰 값과 위 두 값을 비교해서 최댓값을 구하면 된다.

 

👨🏻‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(i -> Integer.parseInt(i)).toArray();

        int[][] dp = new int[nums.length][2];

        dp[0][0] = nums[0]; // 값을 제거하지 않은 경우
        dp[0][1] = 0; // 값을 제거한 경우
        int res = dp[0][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][1] + nums[i], dp[i-1][0]);// 이미 제거한 값들에 현재 꺼 더한 것과 제거하지 않은 값에 현재 값을 제거한 거 비교
            res = Math.max(res, Math.max(dp[i][0], dp[i][1]));
        }
        System.out.println(res);
    }
}