https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 dp 문제로써 점화식을 세워 i번째에 올 max값을 구하면 해결할 수 있는 문제입니다. 소스코드를 작성하면 다음과 같습니다.
소스코드 - python
|
1
2
3
4
5
6
7
8
9
10
11
|
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]
|
cs |
소스코드 - c++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#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;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 16236번: 아기상어(Python, cpp) (0) | 2022.02.15 |
|---|---|
| 백준 숨바꼭질 1697번: 숨바꼭질(Python, cpp) (0) | 2022.02.04 |
| 백준 알고리즘 9461번: 파도반 수열(Python) (0) | 2022.01.31 |
| 백준 알고리즘 2193번: 이친수(Python) (0) | 2022.01.31 |
| 백준 알고리즘 11057번: 오르막 수(Python) (0) | 2022.01.29 |