본문으로 바로가기

임의의 포도주를 마신다고 가정했을 때 해당 포도주를 연속으로 마시지 않은 경우, 1잔 연속으로 마신 경우, 2잔 연속으로 마신 경우로 나누어 최대값을 구할 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[10001];
int a[10001];
int n;

int f(int);

int main() {
  scanf("%d", &n);
  for (int i=1; i<=n; i++) {
    scanf("%d", &a[i]);
  }
  printf("%d\n", f(n));
  return 0;
}

int f(int n) {
  if (n == 0) return 0;
  if (n == 1) return a[1];
  if (n == 2) return a[1] + a[2];
  if (dp[n]) return dp[n];
  int x = a[n] + a[n-1] + f(n-3);// 2잔 연속 마신 경우
  int y = a[n] + f(n-2);// 1잔 연속 마신 경우
  int z = f(n-1);// 0잔 연속 마신 경우
  return dp[n] = max(x, max(y, z));
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 11055: 가장 큰 증가 부분 수열  (0) 2018.05.23
[BOJ] 11053: 가장 긴 증가하는 부분 수열  (0) 2018.05.23
[BOJ] 2156: 포도주 시식  (0) 2018.05.15
[BOJ] 9465: 스티커  (0) 2018.05.15
[BOJ] 2193: 이친수  (0) 2018.05.15
[BOJ] 11057: 오르막 수  (0) 2018.05.15

댓글을 달아 주세요