백준 2156 - 포도주 시식

Java

2156 번 - 포도주 시식

문제

접근 방법

Top-down DP 문제이며, 점화식을 통해 해결하는 문제이다.

해결 키워드는, 마지막(n) 잔을 마셨을 때 하루 전 N-1 일째에 와인을 마시는지 마시지 않는지를 기준으로 점화식을 세운다.

n과 n - 1일째에 와인을 마셨을 때, 연속으로 3일을 마실 수 없다.
따라서 n - 3일 때의 가장 높은 값 dp[n-3]에 n일, n-1일의 와인 양을 합한다.

n일은 마셨지만 n - 1일에 와인을 마시지 않았을 때, 연속하지 않으므로 n - 2일 때의 가장 높은 값에 더한다.

식으로 정리하면 다음과 같다.

1. dp[n] = dp[n-2] + array[n]
2. dp[n] = dp[n-3] + array[n-1] + array[n]

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	int[] arr = new int[n];
    	int[] dp = new int[n];

    	for(int i = 0; i < n; i++) {
    		arr[i] = stoi(br.readLine());
    	}

    	dp[0] = arr[0];
    	if(n >= 2)
    		dp[1] = arr[1] + dp[0];

    	for(int i = 2; i < n; i++) {
    		if(i >= 3) {
    			dp[i] = Math.max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]);		// 점화식
    		}
    		else {
    			dp[i] = Math.max(arr[i] + arr[i - 1], arr[i] + arr[i - 2]);					// 포도주가 3개 미만일 경우 점화식을 걸 수 없으므로 최대값을 구한다.
    		}
    		dp[i] = Math.max(dp[i], dp[i - 1]);		// 2번 이상 안먹는 경우
    	}

    	System.out.println(dp[n - 1]);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

dp Top down 정복 시작

후기

개선할 점