[Python] BOJ 2156 - 포도주 시식

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

2156번: 포도주 시식

간단한 DP문제이다.

1. 우선 dp배열을 N만큼 선언해주고, 포도주의 양을 입력받아 grape배열에 넣는다.

 

2. N==1일 때는 포도주가 1개이므로 grape[0]을 출력하고, N==2일 때는 두 잔 다 마시면 되니

   grape[0] + grape[1]을 출력한다.

 

3. N이 3개이상일 때부터 Bottom-Up방식으로 dp테이블을 갱신해주면 된다.

 

# i번째 잔을 고를 때 최댓값은 다음 3가지 케이스 중 최댓값이다.

    a. i-2번째 잔까지 최대로 마시고(dp[i-2]) 현재 i번째 잔을 마시는경우

    b. i-3번째 잔까지 최대로 마시고(dp[i-3]) 현재 i번째 잔과 i-1번째 잔을 마시는 경우

    c. i-4번째 잔까지 최대로 마시고(dp[i-4]) 현재 i번째 잔과 i-1번째 잔을 마시는 경우

 

4. dp배열 중 최댓값을 출력한다.

N = int(input())
dp = [0] * N
grape = []
for _ in range(N):
	grape.append(int(input()))
if N == 1:
	print(grape[0])
elif N == 2:
	print(grape[0] + grape[1])
else:
	dp[0] = grape[0]
	dp[1] = grape[0] + grape[1]
	dp[2] = grape[2] + max(grape[1], grape[0])
	for i in range(3, N):
		dp[i] = max(dp[i-2] + grape[i], dp[i-3] + grape[i-1] + grape[i], dp[i-4] + grape[i-1] + grape[i])

	print(max(dp))

(solved.ac 티어: 실버 1)

 

# 처음에 a케이스와 b케이스만 고려해서 최댓값을 구했는데, [100, 100, 1, 1, 100, 100]과 같은 케이스에서

  중간 1 두개를 뛰어 넘고 100, 100을 선택하는게 최대인 반례가 있어서 c케이스까지 고려해주었다.