▶실버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 |