백준 2156번 - 포도주 시식

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

2156번: 포도주 시식

 

 

 

 

주어진 배열에서 연속해서 3개까지 선택할 수 없고 최댓값을 구하는 문제로 이전에 풀었던 계단오르기(https://www.acmicpc.net/problem/2579)와 비슷한 문제이다. 계단오르기에서는 도착 지점을 무조건 선택해야 하지만 포도주 시식에서는 상관 없다. 그래서 선택하지 않는 경우를 추가하며 경우의 수가 하나 더 늘었다.

 

 

 

 

 

초기값 (n = 1, n= 2)

dp[1] = glass[1]

dp[2] = glass[1] + glass[2]

 

 

n > 2 일때,

case 1

n- 3   dp

n-2

n-1 선택

n 선택

dp[n] = glass[n] + glass[n - 1] + dp[n - 3]

 

 

case 2

n- 3

n-2   dp

n-1

n 선택

dp[n] = glass[n] + dp[n - 2]

 

 

case 3

n- 3

n- 2

n- 1   dp

n 선택X

dp[n] = dp[n - 1]

 

 

3개 중 최댓값을 선택하면 된다.

 

 

 

 

 

코드

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

public class WineTasting {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		
		int[] glass = new int[n + 1];
		
		for(int i = 1; i <= n; i++) {
			glass[i] = Integer.parseInt(br.readLine());
		}
		
		int[] dp = new int[n + 1];
		
		dp[1] = glass[1];
		
		if(n >= 2) {
			dp[2] = glass[1] + glass[2];
		}
		
		for(int i = 3; i <= n; i++) {
			dp[i] = Math.max(dp[i - 1], Math.max(glass[i - 1] + dp[i - 3], dp[i - 2]) + glass[i]);
		}
		
		System.out.println(dp[n]);
	}

}

 

 

입력값인 n이 1부터이기 때문에 dp[2]에는 조건을 달아주는 것을 잊지 말아야 한다. 조건을 안 달면 에러가 난다.

 

 

 

 

 

결과