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

 

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

2156번: 포도주 시식

풀이

 이 문제는 계단오르기와 비슷한 유형의 문제이다. 우선 이전 포스팅에서도 말했듯이 현재 위치에서의 연속된 수를 구해서 풀이를 하는것이 아닌 경우를 나눠서 진행해야한다. 그러나 계단오르기와 다른점이 있다면 마지막 포도주는 선택을 안해도 된다는 것이다. 여기서 나는 조금 헤매었는데 결국은 dp중 최대값을 계속해서 선택을 하면 된다는 것이다. 

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

여기서 find(x-1)이랑 x까지의 최대 합중 최대인 수를 계속해서 구해나가다보면 최대값만 저장할수있게 되어 답을 구할수있다.

아래는 내가 참고하였던 블로그 포스팅 글이다.

https://st-lab.tistory.com/135

[백준] 2156번 : 포도주 시식 - JAVA [자바]

코드

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

class Main{


    public static int arr[];
    public static Integer dp[];
    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = new int[n+1];
        dp = new Integer[n+1];

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

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

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

    public static int find(int x){
        if(dp[x]==null)
            dp[x] = Math.max(Math.max(find(x-2), find(x-3) + arr[x-1])+arr[x], find(x-1));
        return dp[x];
    }

}