[백준][C++/Python] 2156번: 포도주 시식 (255)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

2156번: 포도주 시식

 

생각의 흐름

 

우선 dp[i]에 대한 정의부터하고 시작해야겠다 생각했다. 우리의 dp[i]는 i번째 포도주 까지 마셨을때의 최대값 을 나타낸다.

 

그럼 연속된 3개가 오지 않으면서 i번 째 최대로 마시려면 어떠한 경우들이 있을까?

총 3가지 경우가 존재한다.

 

1) i번째 포도주를 마시면서(arr[i]), i-2번째까지의 최대합(DP[i-2]) 포도주를 마시는 경우

2) i번째 포도주를 마시면서(arr[i]), i-1번째(arr[i-1]), i-3번째까지의 최대값(dp[i-3]) 포도주를 마시는 경우

3) i번째 포도주를 마시지 않는 경우, i-1번째 까지의 최대값 (dp[i-1])

 

이를 그림으로 보면 다음과 같다.

순서대로 그림으로 그려보았다!

 

이를 점화식으로 풀어 코드로 해결하면 간단하다.

 

나의 코드

1) C++

#include <bits/stdc++.h>
using namespace std;
int arr[10001];
int dp[10001];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int num;
	cin >> num;
	
	for(int i = 1; i <= num; i++){
		cin >> arr[i];
	}
	
	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];
	
	for(int i = 3; i <= num; i++){
		dp[i] = max(dp[i-3]+arr[i-1]+arr[i], max(dp[i-2]+arr[i], dp[i-1]));
	}
	
	cout << dp[num];
	
	return 0;
}

 

 

2) Python

import sys

N = int(sys.stdin.readline())
arr = [0]
for i in range(N):
    arr.append(int(sys.stdin.readline()))

DP = [0 for _ in range(N + 1)]

DP[1] = arr[1]
for i in range(2, N+1):
    DP[i] = max(DP[i-3] + arr[i-1] + arr[i], DP[i-2] + arr[i], DP[i-1])

print(DP[N])