[백준] 13398 연속합 2

 

 

 

문제 출저

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

13398번: 연속합 2

 

 

 

문제 풀이

수열에서 연속하는 몇 개의 수를 선택해 가장 큰 합을 구해야 한다. 이 때, 한 개의 수는 선택하지 않아도 된다. 

 

DP를 이용하여 문제를 풀었습니다.

다만 숫자를 하나 뺄 때, 빼지 않을 때 2가지 경우의 수를 염두해야 합니다. 

 

dp = new int[n][2];

0은 빼지 않았을 경우, 1은 뺀 경우입니다. 

 

dp[n][0] 일 때는 뻰 경우 입니다. 

전의 값(i - 1)과 수열의 더한 값, 수열의 값을 비교하여 더 큰 값을 저장합니다. 

dp[i][0] = Math.max(dp[i-1][0] + board[i], board[i])

 

dp[n][1] 일 때는 숫자 하나를 제외한 경우 입니다. 

하나를 제외하지 않은 dp의 이전값 ( dp[i-1][0] ) , 하나를 제외한 dp에서 수열의 값을 더한 값(dp[i -1][1] + board[i])을 비교하여 더 큰 값을 저장합니다. 

dp[i][1] = Math.max(dp[i-1][0], dp[i-1][1] + board[i])

 

answer 변수를 하나 선언하여 dp[i][0], dp[i][1] 값 중 큰 값을 업데이트하여 최종 정답을 구합니다. 

 

 

 

소스 코드

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

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

public class Main {

    static int n;
    static int[] board;
    static int[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        board = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }



        dp = new int[n][2];

        dp[0][0] = board[0];
        if (board[0] > 0) dp[0][1] = board[0];
        else dp[0][1] = 0;

        int answer = board[0];

        for (int i = 1; i < n; i++) {

            // 특정 수를 제거하지 않을 경우
            dp[i][0] = Math.max(dp[i - 1][0] + board[i], board[i]);

            // 특정 수를 제거하는 경우
            // 1. 현재 위치의 특정 수를 제거한 경우
            // 2. 현재 위치 이전에 특정 수를 제거한 경우
            dp[i][1] = Math.max(dp[i-1][0], dp[i - 1][1] + board[i]);

            answer = Math.max(answer, Math.max(dp[i][0], dp[i][1]));
        }

        System.out.println(answer);




    }

}