카드구매하기2 백준 16194번

문제

카드구매하기2 백준 16194번

리뷰

이전에 풀었던 카드구매하기 문제와는 반대로 '최소값'을 구하는 문제다.

[P[i] 에는 카드팩의 값을 저장한다.

MinCost[i] 에는 i장을 샀을 때의 최소값을 저장하는데, 처음에는 P[i] 값을 저장하고 시작한다.

4장을 산다면,

MinCost[1] + P[3] 와 MinCost[4] 를 비교한다.

MinCost[2] + P[2] 와 MinCost[4] 를 비교한다.

MinCost[3] + P[1] 와 MinCost[4] 를 비교한다.

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int P[10001];
int MinCost[1001];

int main(void){

    freopen("input.txt", "rt", stdin);

    int n = 0, input = 0;

    scanf("%d", &n);

    for(int i = 1; i <= n; i++){
        scanf("%d", &input);
        P[i] = input;
    }    

    MinCost[1] = P[1];    

    for(int i = 1; i <= n; i++){

        MinCost[i] = P[i];

        for(int j = 1; j <= i; j++){

            int temp = min(MinCost[i], MinCost[i-j] + P[j]);

            if(temp < MinCost[i]){
                MinCost[i] = temp;
            }
        }
    }

    printf("%d", MinCost[n]);

    return 0;
}