백준 2156 포도주 시식 JAVA (DP)

1. 문제

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

2156번: 포도주 시식

 

2. 설명

반례를 생각못해서 틀렸었다.

연속해서 3잔을 못마신다는 의미에서 저번에 푼 계단 오르기(백준-2579) 문제랑 비슷했다.

따라서 식 구하는 것도 비슷하게 구하면 된다.

하지만 저번 문제와 다른점으로 이 문제에선 포도주를 연속해서 2번이상 안마실 수 있다.

따라서 이 반례를 고려해서 dp[n]을 구할 때 dp[n-1]과 비교하여 큰 값을 넣어줬다.

 

3. 코드

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 포도잔 개수
		int[] wine = new int[10001];
		int[] dp = new int[10001];
		
		for(int i=1; i<=n; i++) {
			st = new StringTokenizer(br.readLine());
			wine[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[1] = wine[1];
		dp[2] = wine[1]+wine[2];
		
		for(int i=3; i<=n; i++) {
			dp[i] = Math.max(dp[i-2]+wine[i], dp[i-3]+wine[i-1]+wine[i]);
			dp[i] = Math.max(dp[i-1], dp[i]);
		}
		System.out.println(dp[n]);
	}
}