[백준] 2156번: 포도주 시식

ByWindow·2021년 8월 10일
0

Algorithm

목록 보기
44/104
post-thumbnail

📝문제

점화식을 생각해내는 것이 좀 어려웠다.
해당 인덱스에서의 가장 많이 마실 수 있는 포도주 양을 dp 배열에 저장해야되는데
생길 수 있는 경우의 수들을 생각해내서 이것을 식으로 풀어내는 것에 고민을 했다.

dp[i] 값의 경우의 수
1. wine[i] + wine[i-1] + dp[i-2] : dp[i-1]이 아닌 이유는 3잔 이상 연속으로 못 마시기 때문
2. wine[i] + dp[i-2] : 이것 또한 위와 마찬가지
3. dp[i-1] : 예시 입출력에서와 같이 이전 인덱스의 값이 그대로 옮겨질 수도 있다.

여러가지 예시들을 대입해보면서 찾아내었고, 세 가지 경우의 수 중 가장 큰 값을 dp[i]에 놓았다.

📌코드

package Baekjoon;

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

public class BOJ2156 {
    public static void main(String[] args) throws IOException{

        /**
         * dp[i]는
         * dp[i-1]과
         * wine[i]+wine[i-1]+dp[i-3]과
         * wine[i]+dp[i-2]
         * 중 큰 값
         */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int[] wine = new int[n+1];

        for(int i = 1; i < n+1; i++){
            st = new StringTokenizer(br.readLine());
            wine[i] = Integer.parseInt(st.nextToken());
        }
        int[] dp = new int[n+1];
        dp[1] = wine[1];
        dp[2] = wine[1] + wine[2];

        for(int i = 3; i < dp.length; i++){
            dp[i] = Math.max(Math.max(wine[i] + wine[i-1] + dp[i-3], dp[i-1]), wine[i]+dp[i-2]);
        }
        System.out.println(dp[n]);
    }
}
profile
step by step...my devlog

0개의 댓글