[BAEKJOON] 2156 포도주 시식

문제 요악

• 알고리즘 분류: 동적 계획법
• 난이도: Silver1
• 문제 요약
  • 포도잔이 N개로 나열이 되어있다.
  • 연속으로 놓어 있는  3잔은 못 마신다. 
  • 최대로 마실수 있는 포도주 양을 출력해라
• 사이트 주소: https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

문제 풀이

동적 계획법 관련 내용은 아래 사이트에 참조 하면된다.

https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95

동적 계획법 - 나무위키

문제 접근 방법 

 이번 문제도 모든 경우의 수를 구할려면 시간초과로 인해서 DP로 풀어야 한다. 나열되어 있는 포도잔이 연속으로 3개를 못마셔서 최대 2개 마신다고 생각 하고 구해야 한다. N이 1이 거나 2일때는 나열 되어있는 포도잔을 다 마셔야 하고 N이 3일 경우에는 (첫번째 , 두번째), (첫번째, 세번째), (두번째, 세번째) 중 가장 큰값을 출력하면된다. N이 4일 경우에는 (첫번째, 두번째, 네번째), (첫번째, 세번째, 네번째), (두번째, 세번째) 중 가장 큰값을 보면 된다. N이 3일때 고정이지만 N이 4이상인 경우에는 나올수 있는 경우를 보면 아래와 같다.

• i번째 잔을 마시는 경우
  • i번째와 i-1번째와  i-3번째 까지 최대 마신 포도주
  • i번째와 i-2번째 까지 최대 마신 포도주
• i번째 잔을 안마시는 경우
  • i-1번째 까지 최대 마신 포도주

 위 3가지 경우의 수를 구하면 된다. N이 3일때 까지는 고정으로 위 사항으로 구현 하면되고 N이 4일때 부터는 아래와 같은 경우의 수중 가장 큰값을 구하면 된다.

Code

Python

import sys
input = sys.stdin.readline

n = int(input())
array = [int(input()) for _ in range(n)]

dp = [array[0]]

if n > 1:
    dp.append(array[0] + array[1])
if n > 2:
    dp.append(max(array[2] + array[1], array[2] + array[0], dp[1]))
for i in range(3, n):
    dp.append(max(array[i] + array[i-1] + dp[i-3], array[i] + dp[i-2], dp[i-1]))

print(dp[-1])

Java

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] array = new int[n];
		for(int i = 0; i < n; i++) {
			array[i] = Integer.parseInt(br.readLine());
		}
		int[] dp = new int[n];
		dp[0] = array[0];
		if(n > 1) dp[1] = array[0] + array[1];
		if(n > 2) { 
			dp[2] = Math.max(array[1] + array[2], array[0] + array[2]);
			dp[2] = Math.max(dp[2], dp[1]);
		}
		for(int i = 3; i < n; i++) {
			dp[i] = Math.max(dp[i-2], dp[i-3] + array[i - 1]);
			dp[i] = Math.max(dp[i-1], dp[i] + array[i]);
		}
		System.out.println(dp[n-1]);
	}
			
}