백준 알고리즘 11052번: 카드 구매하기(Python)

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

문제 해결을 위한 과정

이 문제의 경우 dp 문제로써 점화식을 세워 i번째에 올 max값을 구하면 해결할 수 있는 문제입니다. 소스코드를 작성하면 다음과 같습니다.

---

소스코드 - python

n = int(input())
data = list(map(int, input().split()))
dp = [0] * n
dp[0] = data[0]
 
for i in range(1, n):
  dp[i] = max(data[i], dp[i-1] + dp[0])
  for j in range(i//2+1):
    dp[i] = max(dp[i], dp[j] + dp[i-j-1])
 
print(dp[n-1]

---

소스코드 - c++

#define MAX 1001
#include <bits/stdc++.h>
 
using namespace std;
 
int main(void) {
    int n, dp[MAX], data[MAX];
    scanf("%d", &n);
 
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &data[i]);
    }
    dp[0] = data[0];
 
    for (int i = 1; i < n; i++) {
        dp[i] = max(data[i], dp[i - 1] + dp[0]);
        for (int j = 0; j < i / 2 + 1; j++) {
            dp[i] = max(dp[i], dp[j] + dp[i - j - 1]);
        }
     }
 
    printf("%d", dp[n - 1]);
    return 0;
}