[백준 2156] 포도주 시식 (Java) - DP

[문제링크]

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

2156번: 포도주 시식

[풀이소스]

package algorithm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Dp2156 {
    public static int[] glassWine; // 각 잔에 담긴 포도주 양
    public static int[] totalWine; // i번째 까지 먹었을때의 최대 포도주 양 
    public static int maxWine;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        
        int glassCount=Integer.parseInt(br.readLine());
        
        // 점화식에서 앞에 세개까지 필요하기때문에 0, 0, 0 잡고 활용
        //   => 따라서 +3해서 배열 선언
        glassWine=new int[glassCount+3];
        totalWine=new int[glassCount+3];
        
        for(int i=0; i<glassCount; i++) {
            // 3번째부터 입력값을 포도주 양 배열에 저장 (앞에 3칸 비우기)
            glassWine[3+i]=Integer.parseInt(br.readLine());
        }
        
        // 점화식 작성하여 결과값 도출
        for(int i=3;i<glassWine.length;i++) {
            int drink0=totalWine[i-1];
            int drink1=totalWine[i-2]+glassWine[i];
            int drink2=totalWine[i-3]+glassWine[i-1]+glassWine[i];
            // 3가지 경우 중 최대값
            maxWine= Math.max(drink0, Math.max(drink1, drink2));
            // 최대값을 최대값배열에 넣기!
            totalWine[i]=maxWine;
        }
        System.out.println(maxWine);
    }
 
}
 

 

 

 

[느낀점]

    - DP에서 가장 중요한 것은 점화식

    - 점화식에서 사용될 범위(n의 연관범위)만큼의 '0'의 저장공간 필요!!