백준 알고리즘 기초/다이내믹 프로그래밍
[백준][DP] 카드 구매하기2
코딩고치
2019. 9. 22. 00:10
1. 문제 주소
16194번: 카드 구매하기 2
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
2. 문제
이전 카드 구매하기 문제에서는 n개의 카드를 살 때 금액의 최댓값을 구하는 문제였다. 이 문제는 그 반대로 최솟값을 구하는 문제이다. 최솟값을 구하는 문제기 때문에 초기값 설정에 주의를 해야 한다.
[백준][DP] 카드 구매하기
1. 문제 주소 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acm..
codingcocoon.tistory.com
3. 소스 코드
1. Bottom-up
|
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
26
27
28
29
30
31
|
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void)
{
int n;
cin >> n;
vector<int> p(n+1);
vector<int> d(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> p[i];
d[i] = p[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i ; j++)
{
d[i] = min(d[i], p[j] + d[i - j]);
}
}
cout << d[n] << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
2. Top-down
|
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
26
27
28
29
30
31
32
33
34
35
36
37
|
#include <iostream>
#include <algorithm>
using namespace std;
int p[1001];
int d[1001];
int topdown(int n)
{
if (n == 0) return 0;
if (d[n]) return d[n];
int result = p[n];
for (int i = 1; i <= n; i++)
{
result = min(result, topdown(n - i) + p[i]);
}
return d[n]=result;
}
int main(void)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> p[i];
}
cout << topdown(n) << '\n';
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|