백준 16194번 카드 구매하기 2

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

16194번: 카드 구매하기 2

 

풀이

DP(Dynamic programming) 문제입니다!

bottom - up 방식으로 이 문제를 해결해보자면,

각 카드팩의 값을 p[1~n] 이라고 두면

카드 1개를 갖기 위한 금액의 최솟값(=d[1])은 p[1] 

카드 2개를 갖기 위한 금액의 최솟값은 min(p[2],d[1]+p[1])

카드 3개를 갖기 위한 금액의 최솟값은 min(p[3],d[2]+p[1],d[1]+p[2])

카드 4개를 갖기 위한 금액의 최솟값은 min(p[4],d[3]+p[1], d[2]+p[2], d[1]+p[3])

...

카드 n개를 갖기 위한 금액의 최솟값은 min(p[n], d[n-1]+p[1], d[n-2]+p[2], ..., d[1]+p[n-1])

이므로

2중 for문으로 dp를 구할 수 있다.

 

소스 코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int p[1001];
int d[1001];
int main()
{
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        d[i] = p[i];
    }
    
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            d[i] = min(d[i], d[i - j] + p[j]);
        }
    }
    printf("%d", d[n]);
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~