백준 16194 - 카드 구매하기(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16194

16194번: 카드 구매하기 2

최소한의 금액으로 N개의 카드를 정확하게 살 때 드는 비용을 구하는 문제입니다.

 

문제 예시에서 4개를 사려고 할 때 

1개 -> 1원 / 2개 -> 5원 / 3개 -> 6원 / 4개 -> 7원이 든다고 할 때, 드는 최소 비용은 1개를 4개 사는 4원일 것입니다.

 

이를 구하는 과정을 생각해보면

1. 3개 사는 최소 금액 + 1개 금액

2. 2개 사는 최소 금액 + 2개 금액

3. 1개 사는 최소 금액 + 3개 금액

4. 4개 금액

-> 이 4개를 비교해서 구했습니다.

 

그렇다면 N개를 사기 위해서는 1~N-1까지를 구매하는 최소 금액을 알고 있어야한다는 것이며

-> 이는 Dp로 풀 수 있는 문제입니다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define INF 987654321

using namespace std;

int N;
int dp[1001];
int cost[1001];

void solve(){
    dp[1] = cost[1];
    dp[2] = min(cost[2], cost[1]*2);
    for(int i = 3; i <= N; i++){
        dp[i] = INF;
        for(int j = 0; j <= i; j++){
            dp[i] = min(dp[i], cost[j] + dp[i-j]);
        }
    }
    cout << dp[N];
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> cost[i];
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.