[백준] 2156 포도주 시식 - 동적계획법(DP, Dynamic Programming) JAVA

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

2156번: 포도주 시식

코드설명

동적계획법(DP, Dynamic Programming)를 활용합니다.

 

문제의 로직이 2579 : 계단오르기 와 매우 유사하지만, 다릅니다.

 

 

문제 로직입니다.

각 위치에서 포도주를 마실 수 있는 최대의 양을 dp[] 라고 선언합니다.

 

첫번째 포도주를 마시는 경우,

dp[1] = arr[1] 입니다.

 

두번째 포도주를 마시는 경우,

dp[2] = arr[1] + arr[2] 입니다. ( 두개의 포도주를 연속적으로 마시는것이 무조건적으로 최대값입니다. )

 

세번째 포도주를 마시는 경우,

dp[3] = Math.max(arr[1] + arr[2], arr[1] + arr[3], arr[2] + arr[3] ) 입니다. 3개의 포도주를 연속해서 오르지 못하니 arr[1] + arr[2] + arr[3] 은 불가합니다.

이 문제에서 계단오르기와 다른점이 있습니다. 

계단 오르기 문제같은경우 dp[3] 이라고할때 해당 계단을 무조건 밟아야만 했습니다.

하지만 포도주 문제 같은경우, 해당 포도주를 마시지 않은 경우. 즉, arr[1] + arr[2] 의 포도주를 먹고 arr[3]은 먹지 않은 경우도 고려할 수 있으므로 하나의 로직이 더 추가됩니다.

 

 

네번째 포도주를 마시는경우는

dp[4] = Math.max(dp[3], arr[1] + arr[2] + arr[4], arr[1] + arr[3] + arr[4], arr[2] + arr[4] ) 입니다.

여기서 겹치는 것을 볼 수 있습니다.

 

1. arr[1] + arr[2] + arr[4] 는 첫번째, 두번째, 네번째 포도주를 마시는 것을 의미합니다.

2. arr[1] + arr[3] + arr[4]는 첫번째, 세번째, 네번째 포도주를 마시는 것을 의미합니다.

3. arr[2] + arr[4] 는 두번째, 네번째 포도주를 마시는 것을 의미합니다. 
4. dp[3] ( arr[4]를 마시지 않는 경우 ) -> arr[1] + arr[2] + arr[1] + arr[3], arr[2] + arr[3]

 

문제를 보면, 첫번째 Case와 세번째 Case에서 arr[2]가 겹치는것을 볼 수 있습니다.

첫번째 Case의 arr[1] + arr[2] + arr[4] 와 arr[2] + arr[4]는 arr[2] 값이 겹치는데 이떄 arr[2]값은 앞서서 우리가 dp[2]라고 정리해놓았습니다. 그렇기에 dp[2] + arr[4] 입니다. 일반화하면, dp[i-2] + arr[i] 입니다. 여기서 헷갈릴 수 잇는 점은 dp[i-3] + arr[i-2] + arr[i]로 표현하는게 맞지 않나라는 생각이 들 수 있습니다. 하지만, 그렇게 할경우 arr[2] + arr[4]값은 고려하지 않으면서 최대값을 구할 수 없습니다. 이미 dp[i-2]를 통하여 앞의 것들의 최대값을 가져온 값을 가져와야 dp[i]가 최대값으로 갱신됩니다. 

 

두번쨰 Case의 arr[1] + arr[3] + arr[4]같은경우가 헷갈립니다. 여기서 dp[3] + arr[4]를 해야하는건가? 라는 궁금증이 생깁니다. 하지만, dp[3]을 더할경우 dp[3]의 최대값이 만약 arr[2]+arr[3] 이었다면 arr[4]도 더해짐으로써 3개의 계단을 동시에 이동한것과 같이 됩니다. 그것은 규칙에 위반되므로 우리는 시작점의 DP값을 더해야만 계단을 3계단 연속적으로 이동하는 경우를 피할 수 있습니다. 여기서 시작점은 arr[1] 입니다. 그러므로 dp[1]을 더하면 되고, 식으로 일반화한다면 dp[i-3] + arr[i-1] + arr[i] 로 정리할 수 있습니다.

 

 

문제에서 포도주를 마시지 않더라도 해당 위치까지의 포도주를 최대로 많이 먹은 횟수를 고려해야한다는점이 계단 오르기 문제와 다릅니다. ( 계단 오르기 문제는 마시지 않는 경우는 고려하지 않기에, 더 단순 )

코드

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

public class Main {
	public static int T, N, M;
	public static int answer = 0;
	public static int[] arr;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	arr = new int[N+1];
    	dp = new int[N+1];
    	
    	for(int i=1;i<N+1;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	
    	dp[1] = arr[1];
    	if( N == 1) {
    		System.out.println(dp[1]);
    		return ;
    	}
    	
    	dp[2] = arr[1] + arr[2];
    	if( N == 2) {
    		System.out.println(dp[2]);
    		return ;
    	}
    	dp[3] = Math.max(arr[1] + arr[2], Math.max(arr[1] + arr[3], arr[2] + arr[3]));
    	for(int i=4;i<=N;i++) {
    		dp[i] = Math.max(dp[i-1], Math.max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]));
    	}

    	System.out.println(dp[N]);
    	
    	
    }
    
}

 

재귀와 메모이제이션을 활용합니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static int[] arr = new int[10001];
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		for(int i=0;i<N; i++) {
			Arrays.fill(cache[i], -1);
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(DFS(0, 0));
		
	}
	static int[][] cache = new int[10001][3];
	static int DFS(int now, int state) {
		if(now == N) return 0;
		if(cache[now][state] != -1) return cache[now][state];
		int ret = 0;
		if(state < 2)
			ret = DFS(now + 1, state + 1) + arr[now];
		ret = Math.max(ret, DFS(now + 1, 0));
		
		
		return cache[now][state] = ret;
	}
}