본문으로 바로가기

다이나믹 프로그래밍을 사용하여 임의의 개수의 붕어빵을 팔았을 대 낼 수 있는 최대 수익을 계산한다. 모든 경우를 다 탐색하기 때문에 완전 탐색이라고 할 수도 있겠다.

#include <cstdio>

int dp[1001];
int a[1001];
int n;
int ans;

int f(int);// 붕어빵 n개를 팔았을 때 낼 수 있는 최대 수익

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 == 1) return a[1];
  if (dp[n]) return dp[n];

  int max = 0;
  for (int i=1; i<=n; i++) {
    int tmp = a[i] + f(n-i);
    max = max > tmp ? max : tmp;
  }

  return dp[n] = max;
}

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

[BOJ] 11057: 오르막 수  (0) 2018.05.15
[BOJ] 10844: 쉬운 계단 수  (0) 2018.05.15
[BOJ] 11052: 붕어빵 판매하기  (0) 2018.05.15
[BOJ] 9095: 1, 2, 3 더하기  (0) 2018.05.15
[BOJ] 11727: 2xn 타일링 2  (0) 2018.05.15
[BOJ] 11726: 2xn 타일링  (0) 2018.05.15

댓글을 달아 주세요