[JAVA] 백준 2156 포도주 시식

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

2156번: 포도주 시식

 

- 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

 

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

 2. 연속으로 놓여 있는 3잔은 모두 마실 수는 없다. 

 

- 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램

 

 

문제 풀이

 

[백준] 2156번. 포도주 시식 (velog.io)

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

 

[C언어 백준 풀이][Silver I] 2156번 : 포도주 시식 / 10844번 : 쉬운 계단 수 / 14888번 : 연산자 끼워넣기 (tistory.com)

[C언어 백준 풀이][Silver I] 2156번 : 포도주 시식 / 10844번 : 쉬운 계단 수 / 14888번 : 연산자 끼워넣기

 

 

memo[n]  = i번째 잔까지 탐색했을 떄 마실 수 있는 최대 포도주의 양

podoju[n] = 각 포도주의 양

 

i번째 와인의 최대치를 선택하는 점화식 

 

1) n번째 와인을 선택하지 않는 경우 

 memo[i] = memo[i-1]

 

2) n-1번째 와인을 선택하지 않는 경우 

memo[i]  = memo[i-2] + memo[i]

 

3) n-2번째 와인을 선택하지 않는 경우 

memo[i] = memo[i-3] + memo[i-1] + memo[i]

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main 
{
    static int podoju[];
    static int memo[];
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        podoju = new int[n+1];
        memo = new int[n+1];
        
        
        for(int i=1; i<=n; i++)
        {
        	StringTokenizer st = new StringTokenizer(br.readLine());
            podoju[i] = Integer.parseInt(st.nextToken());
        }
        
        memo[1] = podoju[1];
        
        if(n>1)
        {
            memo[2] = podoju[1] + podoju[2];
        }
        
        for(int i=3; i<=n; i++)
        {
            memo[i] = Math.max(memo[i-1], Math.max(memo[i-2]+podoju[i], memo[i-3]+podoju[i-1]+podoju[i]));
        }
        
        bw.write(memo[n]+"");
        
        bw.flush();
        bw.close();
    }
}