https://www.acmicpc.net/problem/16194
시간 제한 | 메모리 제한 | solved.ac 티어 |
1초 | 256MB | 실버1 |
문제
요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.
PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.
- 전설카드
- 레드카드
- 오렌지카드
- 퍼플카드
- 블루카드
- 청록카드
- 그린카드
- 그레이카드
카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.
민규는 지난주에 너무 많은 돈을 써 버렸다. 그래서 오늘은 돈을 최소로 지불해서 카드 N개를 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.
예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최솟값은 4원이다. 1개 들어있는 카드팩을 4번 사면 된다.
P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 2개 들어있는 카드팩을 2번 사면 4원이고, 이 경우가 민규가 지불해야 하는 금액의 최솟값이다.
카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.
입력
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
출력
첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최솟값을 출력한다.
맨 처음에 작성한 풀이가 dp인줄 알았지만, 다시 생각해보니 결국 브루트포스적 접근이어서 시간초과로 계속 틀렸다(처음에는 브루트포스적으로 푼 것도 모르고 별짓 다했지만 계속 시간초과 난건 안비밀). 이후 어떻게 개선할 지 고민하다가 1149번의 문제 풀이를 응용하였다.
dp의 접근은 하나의 문제를 작은 문제로 쪼개어 그 문제로 큰 문제를 푸는 것이다. i개의 카드를 구매하는 문제는 i-1개를 구매하는 문제로 쪼갤수 있다. 이를 응용하여 n개의 카드를 구매(n < i)할 때의 최소가격을 찾아내고, 이를 n + 1개에서의 최소가격에 반영한다.
#include <bits/stdc++.h>
using namespace std;
vector<int> P;
// vector<vector<int>> memo;
int n;
void input() {
cin >> n;
// memo.resize(n + 1);
// for(int i = 1; i <= n; i++) memo[i].resize(n + 1, 0);
P.resize(n + 1);
for(int i = 1; i <= n; i++) cin >> P[i];
}
// int dp(int x, int card_cnt) { // 알고보니 브루트포스
// if (card_cnt == n) return P[x];
// fill(memo.begin(), memo.end(), 0);
// int cost = 2e4;
// for (int i = 1; i <= n - card_cnt; i++) {
// if (!memo[i][card_cnt + i]) {
// memo[i][card_cnt + i] = dp(i, card_cnt+ i);
// }
// cost = min(cost, P[x] + memo[i][card_cnt + i]);
// }
// return cost;
// }
// void sol() {
// int min_pay = 2e9;
// for (int i = 1; i <= n; i++) {
// min_pay = min(min_pay, dp(i, i));
// }
// cout << min_pay;
// }
void sol() { // 이게 진짜 dp 풀이
vector<int> dp(n + 1, 1e4 + 1);
dp[0] = 0;
for(int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] = min(dp[i], dp[i - j] + P[j]);
}
}
cout << dp[n];
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
input();
sol();
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 1966번 C++ 풀이 (0) | 2022.05.22 |
---|---|
백준 16926번 C++ 풀이 (0) | 2022.05.22 |
백준 3273번 C++ 풀이 (0) | 2022.05.22 |
백준 1339번 C++ 풀이 (0) | 2022.05.22 |
백준 1449번 C++ 풀이 (0) | 2022.05.22 |