[BOJ_16194_RN] 카드 구매하기 2 Problem Solving

문제 출처 : https://www.acmicpc.net/problem/16194

문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming )

해설

이 문제는 정해진 갯수의 카드를 최소값으로 사는 문제이다. 1 ~ N 개의 카드세트가 있을 때, N개의 카드를 가장 싸게 구하는 문제이다. 이 문제는 간단한 부분 문제로 나눌 수 있다. N개의 카드를 살 때 가장 싸게 사는 방법은 선택한 카드의 갯수만큼 가장 싼 값에 산다고 가정했을 때, 이 중 하나일 것이다.

카드 N개를 산다.

카드 N - 1개와 1개를 산다.

카드 N - 2개와 2개를 산다.

...

N - 1개를 산다고 가정하면 N - 1개를 최솟값으로 살 수 있는 경우를 탐색해야한다. 이 때 (N - 1) - 1개와 1개를 산다고 가정하면 N - 2개를 최솟값으로 살 수 있는 경우를 탐색하게된다. 하지만 이값은 맨 처음에서도 계산을 한다. 즉 연산이 중복된다는 소리이다. 이러한 중복되는 DP를 이용하여 줄일 수 있다.

바텀업 ( bottom up ) 방식으로 카드 1개를 살 때의 최솟값, 2개를 살 때의 최솟값 ... N개를 살 때의 최솟값 순서대로 구할 수 있다.

이러한 점화식을 얻을 수 있다.

시간복잡도

이 코드는 바깥 for문이 N 번 안쪽 for문이 1 ~ N번 반복한다. 따라서 시간복잡도는  이다.

카드 구매하기 2 코드 [ C ]

#include <stdio.h>
int ar[1001];
int min(int i, int j) {
    return i < j ? i : j;
}
int main() {
    int i, j, n, c;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i) {
        scanf("%d", ar + i);
        for (j = 1; j < i; ++j) {
            ar[i] = min(ar[j] + ar[i - j], ar[i]);
        }
    }
    printf("%d", ar[n]);
    return 0;
}