DP - 2156(포도주 시식)

2156번: 포도주 시식 (acmicpc.net)

2156번: 포도주 시식

 

3번 연속으로 포도주를 마시면 안되기 때문에 나올 수 있는 패턴은 총 세가지가 있습니다. 

 

O	O	X
O	X	O
X	O	O

이 세가지 패턴을 가지고 패턴의 최대값을 갱신해 나간다면 문제를 해결 할 수 있었습니다. 

package com.company;

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        int wine[] = new int[t+1];
        int drink[] = new int[t+1];
        for(int i = 1; i<=t; i++){// 테스트 케이스 시도 횟수
                int temp = Integer.parseInt(br.readLine());
                wine[i] = temp;
        }

        drink[1] = wine[1];

        if(t>1){ drink[2] = wine[2]+wine[1];}

        for(int j = 3; j<=t; j++){
            drink[j] = Math.max(drink[j-2]+wine[j], Math.max(drink[j-1] , drink[j-3] + wine[j-1]+wine[j]));
        }


        System.out.println(drink[t]);
    }
}

 

부족했던 점

시간을 오래써도 파악이 되지 않아서 다른 코드를 참고 하였습니다. 위의 패턴파악은 했지만 어떻게 구현 할까 고민했는데 점화식 파악에 조금더 익숙해져야 할 것 같습니다.