[백준 2156번] 포도주 시식

문제 링크: 2156번 제목

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

 

"연속으로 놓여 있는 3잔을 모두 마실 수는 없다"라는 조건에서 헤맸다. 내가 생각했던 것은, dp 배열이 이전의 정보를 담고 있는다는 것이었다. 즉 현재의 잔을 마셨을 때, 1번째 전 잔을 마셨을 때, 2번째 전 잔을 마셨을 때를 모두 나누어 생각해보고자 했다. 하지만 이러한 방법은 배열의 중간중간이 비게 되어 바람직하지 못하다.

어떤 잔을 마셨건 이를 저장할 필요없이 이러한 각각의 경우를 36라인과 같이 특정 시점까지의 잔 수를 dp[i-n]으로 살펴본 후 2번째 전 잔까지를 arr[i]로 별도로 더해주면 된다.

 

package baekjoon.problem11053;

import java.util.Scanner;

public class Main {
	public static int max(int a, int b) {
		if (a>b) return a;
		else return b;
	}
	
	public static int max(int a, int b, int c) {
		return max(max(a, b), c);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n+1];
		for (int i = 1; i < n+1; i++)
			arr[i] = sc.nextInt();
		sc.close();
		
		switch (n) {
		case 1: System.out.println(arr[1]); break;
		case 2: System.out.println(arr[1]+arr[2]); break;
		case 3: System.out.println(max(arr[1]+arr[2], arr[1]+arr[3], arr[2]+arr[3]));
		}
		if (n<=3) System.exit(0);
		
		int[] dp = new int[n+1];
		dp[1] = arr[1];
		dp[2] = arr[1]+arr[2];
		dp[3] = max(arr[1]+arr[2], arr[1]+arr[3], arr[2]+arr[3]);
		
		for (int i = 4; i < n+1; i++)
			dp[i] = max(dp[i-1], dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]);
		
		System.out.println(dp[n]);		
	}
}