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

 

www.acmicpc.net/problem/2156

2156번: 포도주 시식

[문제 풀이]

DP를 이용하여 문제를 풀었습니다.

 

이 문제는 숫자가 주어 졌을 때 아래와 같은 두 가지 규칙을 이용하여 포도주를 고를 때 최대로 마실 수 있는 포도주의 양을 찾는 문제입니다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

문제를 푸는 방법은 1 ~ N까지 포도주 양을 확인하며 누적합을 메모제이션 하는 방법입니다. 문제를 풀기 위하여 DP를 이용하였습니다. 문제에 사용 된 점화 식은 아래와 같습니다.

dp[i] = Math.max(dp[i-1],Math.max(arr[i] + dp[i-2], arr[i] + arr[i-1] + dp[i-3]));

 

 점화식을 풀어서 설명드리면 아래처럼 세 가지의 패턴에 대해 비교하여 누적합을 적는 것입니다. 

• i 번째를 고르지 않는 것 (dp[i-1])
• i 번째를 고르고 i-1번째를 고르지 않는 것(arr[i] + dp[i - 2])
• i 번째와 i-1 번째를 고르는 것(arr[i-1] + arr[i-1] + dp[i-3])

이러한 패턴을 점화식으로 나타내서 최대값을 찾는 것입니다.

[코드]

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

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