[JAVA] 백준 2156번 - 포도주 시식

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int arr[] = new int[n];
		int dp[] = new int[n];
		
		//dp[5]의 경우 
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		
		if(n == 1) {
			System.out.println(arr[0]);
			return;
		}else if(n == 2) {
			System.out.println(arr[0]+arr[1]);
			return;
		}else {
			dp[0] = arr[0];
			dp[1] = arr[0]+arr[1];
			dp[2] = Math.max(dp[1],Math.max(arr[0]+arr[2], arr[1]+arr[2]));
			
			for (int i = 3; 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-1]);
		}
	}
}

👨🏻‍💻 결과

 

📕 풀이 방법

3가지의 경우의 수가 있습니다.

1. i-1번째 잔과 i번째 잔을 마실 때 + dp[i-3]
2. i-1번째 잔을 마시지 않고 i번째 잔을 마실 때 + dp[i-2]
3. i번째 잔을 마시지 않을 때 = dp[i-1]

 

🔗 링크

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

2156번: 포도주 시식