본문 바로가기
Algorithm/Baekjoon

2156_포도주 시식

by 모너아링 2023. 1. 16.

▶실버1

풀이

연속으로 3잔을 마실 수 없으므로 2잔을 연속으로 마시면 한 잔은 쉬어야 하는데, 최대의 합을 내기 위해서는 연속 두 잔 이상을 마시지 않으면 안된다.

즉, 1번 잔을 마셨으면 꼭 2번 잔을 마시거나 3번 잔을 마셔야 한다. 2번과 3번을 모두 마시지 않으면 최대 값을 낼 수 없다.

이 점을 참고!

 

예제에서 5번째 잔까지만 표로 나타내면

6 10 13 9 8

여기서 모든 경우의 수는

(1, 2, 4, 5)

(2, 3, 5)

(1, 3, 4)

이다.

 

① (1, 2, 4, 5) => dp[2] + arr[4] + arr[5]

② (2, 3, 5) => dp[3] + arr[5]

③ (1, 3, 4) => dp[4]

 

이를 점화식으로 나타내면

dp[i] = max({ dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i], dp[i - 1] })

 

코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int dp[100001];
int arr[100001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

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

'Algorithm > Baekjoon' 카테고리의 다른 글

10799_쇠막대기  (0) 2023.02.02
17478_재귀함수가 뭔가요?  (0) 2023.01.22
9465_스티커  (1) 2023.01.16
1699_제곱수의 합  (0) 2023.01.13
11660_구간 합 구하기 5  (0) 2023.01.11