백준 2156번 - 포도주 시식

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

2156번: 포도주 시식

 

 

 

이 문제는 계단 오르기 방식과 비슷한 형태의 문제이다.

https://3946.tistory.com/94

백준 2579번 - 계단 오르기

 

 

 

 

먼저 N=5 까지의 경우의 수를 직접 계산해봤고 N=5 일 때를 가정하여 풀었다.

 

 

dp[5] 의 값 중 1+3+4 는 dp[i-1] 의 값을 포함하고 있고

 

 

dp[5] 의 값 중 2+3+5 와 1+3+5 는 dp[i-2] 의 값에 arr[i] 을 더한 값을 포함하고 있다.

 

 

그리고 나머지 1+2+4+5 는 dp[i-3] 값에 arr[i-1] + arr[i] 를 더한 값을 포함하고 있다.

 

 

 

따라서 i가 3 이상일 때 다음과 같은 식이 성립한다.

dp[i] = Math.max(dp[i-1],Math.max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]));

 

 

코드(bottom-up 방식)

import java.io.*;
import java.util.*;

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+1;i++){
        	arr[i] = sc.nextInt();
        }
        dp[0]=0;
        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-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]));
        }
        
        System.out.println(dp[N]);
    }
}