[백준]2156번 포도주 시식(java)

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

2156번: 포도주 시식

백준 2156번 포도주 시식 문제 링크입니다.

핵심

이 문제는 저번에 풀었던 계단 오르기와 매우 유사한 문제이다.

https://kimtaesoo99.tistory.com/31

[백준]2579번 계단 오르기

차이점은 마지막을 선택하는지 안 하는지이다.

정답 코드

import java.util.Scanner;

public class Main
{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];

        for (int i = 1; i<=n; i++){
            arr[i] = sc.nextInt();
        }
        dp[1] = arr[1];

        if (n>=2) dp[2] = arr[1]+arr[2];

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

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

해설

계단 오르기에서 한 것과 매우 비슷하다. 심지어 코드도 한 줄만 바뀌었다.

연속 3개를 고를 수 없으니, for문에 dp [i-2]와 dp [i-3]+arr [i-1] 값을 비교한다.

이것은 i를 선택한다고 가정했을 때 더 큰 값을 고른 것이다.

따라서 dp [i-1]을 비교하여 그전까지 고른 값도 비교해주어야 한다.

 

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.