[백준 2156 ] 포도주 시식 (Java) - 실버1

# 문제                          

2156번: 포도주 시식

2156번: 포도주 시식

 

 

# 접근법                          

구하는것

    마실 수 있는 Max의 포도주 양

조건

1. 연속으로 3잔은 못먹음 ← 얘 때문에 애먹음
2. 포도주 잔의 갯수의 범위는 1 ≤ n ≤ 10,000 임 ← 즉, 음의 정수는 X
3. 포도주의 양은 순서대로 주어진다(순서 바꾸지 못함)

---

DP문제임을 알고 접근했지만, 3개 연속으로 먹지 못한다는 것을 어떻게 해결하면 좋을지 고민을 많이했음.

일단 Top-down 방식으로 푼 블로그도 있던데, 재귀함수로는....지금 내 머리로는 도저히 못풀 것 같고

약간의 도움을 받아서 Bottom-up방식으로 풀어봤다..

처음에 아래의 방식으로 생각해서 풀었더니 예제가 맞게 답이 나와서 자신감 넘치게 제출했더니 틀렸습니다(구체적으로는 ArrayIndex 런타임 에러발생)!!!!ㅋㅋㅋㅋㅋ

알고보니...포도주가 1개뿐이 없을경우, 2개뿐이 없을 경우를 놓쳤다.

이를 조건문 추가해서 제출했더니 드디어 맞았습니다!!!!

 

 

# 풀이                          

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

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

        int[] wine = new int[n];
        int[] dp = new int[n];

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

        dp[0] = wine[0]; //n = 1만 있는 경우

        //아...자꾸 런타임에러 나길래 생각해보니, n = 1인 경우 아래조건이 들어가야함.
        if(n > 1){
            dp[1] = wine[0] + wine[1]; //포도주가 2개 있는 경우
        }
        
        if(n > 2){
            dp[2] = Math.max(dp[1], Math.max(wine[0]+wine[2], wine[1] + wine[2]));
        
            for(int i = 3; i < n; i++){
                dp[i] = Math.max(dp[i-2] + wine[i], Math.max(dp[i-1], dp[i-3] + wine[i-1] + wine[i]));
            }
        }
        
        System.out.println(dp[n-1]);
    }
}