[99클럽 코테 스터디 12일차 TIL] 포도주 시식

 

12일차 문제

링크 : https://www.acmicpc.net/problem/2156

 

 

 

문제 풀이

DP를 사용해 풀이하였다.

다만, DP 배열 초기화할 때 유의해야 한다. -> 런타임 에러 발생 방지

 

1일차 : arr[1]

2일차 : arr[2]

3일차 : Math.max(dp[1], dp[1] + arr[3], dp[0] + arr[2] + arr[3])를 이용해 점화식을 세운다.

 

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

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[] arr = new int[n+1];
        int[] dp = new int[n+1];

        for(int i=1; i<=n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // dp 배열 초기화
        /* 
        n이 1일 경우 런타임에러 발생!!
        dp[0] = 0;
        dp[1] = arr[1];
        dp[2] = arr[1] + arr[2];
         */

        for(int i=1; i<=n; i++) {
            if(i == 1) {
                dp[i] = arr[i];
            } else if(i == 2) {
                dp[i] = arr[i-1] + arr[i];
            } else {
                dp[i] = Math.max(dp[i-1], Math.max(dp[i-2] + arr[i], dp[i-3] + arr[i] + arr[i-1]));
            }
        }

        System.out.println(dp[n]);
    }
}