BOJ 16194. 카드 구매하기 2

BOJ 16194. 카드 구매하기 2

풀이

d[n] = 카드 N개를 갖기 위한 금액의 최솟값. 카드 1개를 p[1]에 구매 -> 남은 카드의 수 i-1 -> p[1] + d[i-1]
카드 2개를 p[2]에 구매 -> 남은 카드의 수 i-2 -> p[2] + d[i-2]
카드 3개를 p[3]에 구매 -> 남은 카드의 수 i-3 -> p[3] + d[i-3]
..
..
카드 N개를 p[N]에 구매 -> 남은 카드의 수 i-N -> p[N] + d[i-N] 

이므로 범위는 1<= j = i 라는 범위가 성립한다.

점화식
d[i] = min( d[i-1] + p[1] , d[i-2]+p[2] ……… )
d[i] = min(p[j] + d[i-j])  , ( 1 <= j <= i )

Bottom-Up

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] d = new int[n + 1];
        int[] p = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            p[i] = sc.nextInt();
        }

        d[0] = 0;
        for (int i = 1; i <= n; i++) {
            d[i] = p[i];
            for (int j = 1; j <= i; j++) {
                d[i] = Math.min(d[i], d[i - j] + p[j]);
            }
        }

        System.out.println(d[n]);
    }
}

import java.util.*

fun main() {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()

    val d = IntArray(n + 1) { 0 }
    val p = IntArray(n + 1) { 0 }

    for (i in 1..n) p[i] = sc.nextInt()

    for (i in 1..n) {
        d[i] = p[i]
        for (j in 1..i) {
            d[i] = kotlin.math.min(d[i], d[i - j] + p[j]);
        }
    }

    println(d[n])
}

Top-Down

import java.util.Arrays;
import java.util.Scanner;

class Main {
    static int[] d = new int[1001];
    static int[] p = new int[1001];
    static int maxValue = 1000 * 10000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            p[i] = sc.nextInt();
        }
        Arrays.fill(d, maxValue);

        sc.close();
        System.out.println(go(n));
    }

    static int go(int i) {
        if (i == 0) return 0;
        if (d[i] != maxValue) return d[i];

        for (int j = 1; j <= i; j++) {
            d[i] = Math.min(d[i], go(i - j) + p[j]);
        }

        return d[i];
    }
}

import java.util.*

val maxValue = 1000 * 10000
val d = IntArray(1001) { maxValue }
val p = IntArray(1001) { 0 }

fun main() {
    val sc = Scanner(System.`in`)
    val n = sc.nextInt()
    for (i in 1..n) p[i] = sc.nextInt()
    println(go(n))
}

fun go(i: Int): Int {
    if (i == 0) return 0
    if (d[i] != maxValue) return d[i]
    for (j in 1..i) d[i] = kotlin.math.min(d[i], go(i - j) + p[j])
    return d[i];
}

풀이소스

github.com/beomjo/algorithm-study/blob/2c55da78e6c32999db1d586ac95660b8774e4653/BOJ/java/16194.java [github.com/beomjo/algorithm-study/blob/2c55da78e6/BOJ/kotlin/16194.kt](https://github.com/beomjo/algorithm-study/blob/2c55da78e6/BOJ/kotlin/16194.kt