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

연속한 3개의 포도주를 마실 수 없다는 조건이 https://www.acmicpc.net/problem/2579 와 비슷해보였다. 저 문제를 풀다가 모르겠어서 방치하고 있었는데 이 김에 이런 유형의 문제를 알아야겠다 싶어서 블로그 글을 작성한다.

우선 문제에서 주어진 조건은

1. 되도록 많은 양의 포도주를 마셔야한다.
2. 연속한 3개의 포도주는 마실 수 없다.

연속한 3개의 포도주는 마실 수 없다.

이 말은 즉,

• 0개가 연속했을 때 -> 가능
• 1개가 연속했을 때 -> 가능
• 2개가 연속했을 때 -> 가능

과 같은 말이다. 따라서 max[i]를 i번째에서 마실수 있는 포도주 양의 최댓값, wine[i]을 i번째에 있는 포도주의 양이라고 하면

max[i] = max[i-1] // 0개연속 ??X
max[i] = wine[i] + max[i-2] //1개 연속 ?XO
max[i] = wine[i] + wine[i-1] + max[i-3] //2개 연속 XOO

가 된다.

0개가 연속했을때는 i-1과 i-2에서 포도주를 마셨는지 안마셨는지 상관없다. 따라서 max[i]는 max[i-1]값과 같다.

1개가 연속했을때는 i-1는 무조건 마시지 않아야한다. 그러나 i-2는 상관이 없다. 따라서 max[i]는 현재 1개연속이므로 wine[i]에 max[i-2]를 더한 값이다.

2개가 연속했을때는 i-1는 무조건 마셔야하고 i-2는 무조건 마시지 말아야한다. 따라서 max[i]= wine[i]+wine[i-1]+max[i-3]이다.

✔ 이렇게 3개의 조건 중 가장 큰 값이 max[i]를 차지하게 된다.

그리고 점화식에서 i-3에 접근을 하므로 반복문을 돌기전에 초기값세팅을 해주어야한다!

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

public class No2156_포도주시식 {
    static int[] wine = new int[10001];
    static int[] max = new int[10001];
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for (int i=1;i<=n;i++) {
            wine[i]=Integer.parseInt(br.readLine());
        }

        max[1]=wine[1];
        max[2]=wine[1]+wine[2];
        max[3]=Math.max(max[2],Math.max(wine[3]+wine[1],wine[2]+wine[3]));//초기값 세팅
      

        for (int i=4;i<=n;i++) {
            max[i]=Math.max(Math.max(max[i-1],wine[i]+max[i-2]),wine[i]+wine[i-1]+max[i-3]);
        }

        System.out.println(max[n]);
    }

}

느낀점

이렇게 dp문제 중 '몇개 이상 연속하지 못하는'조건이 있다면 이런방식으로 접근해야됨을 알게되었다
내일 계단오르기 문제도 풀어봐야겠다 홧팅