GitHubSeob
C++ / 백준 / 2156 / 포도주 시식 본문
문제
https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
문제풀이
OXXOO
OXOO
OXXO
OXO
포도주는 3번 연속 마실수 없다, 경우의 수에서 3번 연속 안 마시고 최댓값을 낼 수 없다.
따라서 N번째를 마신다고 가정했을 때
DP[N] = DP[i-4] + Arr[i-1] or
DP[i-3] + Arr[i-1] or
DP[i-3] or
DP[i-2]
중 최대값에 Arr[N]값을 더한 값이다.
DP[N]은 N번째를 무조건 마신다고 가정하였으므로 N을 마시지 않고 N-1, N-2를 마신 경우가 더 클 수 있기 때문에
1부터 N까지 반복하면서 최댓값을 찾아 출력한다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n = 0;
int i = 0;
cin >> n;
vector<int>DP(n + 4, 0);
vector<int>Arr(n + 4, 0);
for (i = 4; i < n + 4; ++i) {
cin >> Arr[i];
}
for (i = 4; i < n + 4; ++i) {
DP[i] = DP[i - 2];
DP[i] = max(DP[i], DP[i - 3]);
DP[i] = max(DP[i], DP[i - 3] + Arr[i - 1]);
DP[i] = max(DP[i], DP[i - 4] + Arr[i - 1]);
DP[i] += Arr[i];
}
int answer = 0;
for (i = 4; i < n + 4; ++i)
answer = max(answer, DP[i]);
cout << answer;
}
'Baekjoon > Silver' 카테고리의 다른 글
C++ / 백준 / 7569 / 토마토 (0) | 2021.08.09 |
---|---|
C++ / 백준 / 2606 / 바이러스 (0) | 2021.08.09 |
C++ / 백준 / 11053 / 가장 긴 증가하는 부분 수열 (0) | 2021.08.06 |
C++ / 백준 / 9465 / 스티커 (0) | 2021.08.06 |
C++ / 백준 / 2193 / 이친수 (0) | 2021.08.06 |