[BOJ] 백준 [2156] 포도주 시식 JAVA

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

2156번: 포도주 시식

 

문제

 

풀이

조건이 있는 DP 문제이다.

특정 i 번째 포도주를 골랐다는 가정을 하면 두 가지 경우로 나뉜다.

i-1 번째를 선택한 경우 => dp[i] =dp[i-3]+arr[i-1]+arr[i]

i-1 번째를 선택하지 않은 경우 => dp[i] = dp[i-2] + arr[i]

 

그리고 누적합이 그 전 단계가 더 클 경우도 있기때문에 dp[i] 와 dp[i-1] 중 큰 것을 골라야한다.

 

import java.util.*;
import java.io.*;
 
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[1]=arr[1];
        if(n>1)
            dp[2] = arr[1]+arr[2];
 
        for(int i=3;i<=n;i++){
            dp[i] = Math.max(dp[i-1],Math.max(dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i]));
 
        }
        System.out.println(dp[n]);
    }
}