BOJ 11052. 카드 구매하기

BOJ 11052. 카드 구매하기

풀이

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] = max( d[i-1] + p[1] , d[i-2]+p[2] ……… )
d[i] = max(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();
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                d[i] = Math.max(d[i], d[i - j] + p[j]);
            }
        }
        System.out.println(d[n]);
    }
}

fun main() {
    val n = readLine()!!.toInt()
    val d = IntArray(n + 1) { 0 }
    val p = "0 ${readLine()!!}".split(" ").map { it.toInt() }
    for (i in 1..n)
        for (j in 1..i) d[i] = max(d[i], d[i - j] + p[j])
    println(d[n])
}

Top-Down

import java.util.Scanner;

class Main {
    static int[] d = new int[1001];
    static int[] p = new int[1001];

    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();
        }

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

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

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

import java.lang.Math.max
import java.util.*

val d = IntArray(1001) { 0 }
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] > 0) return d[i]
    for (j in 1..i) d[i] = max(d[i], go(i - j) + p[j])
    return d[i];
}

시간 복잡도 1 장부터 n장까지 반복 = O(n)
각 i장의 최댓값 반복 = O(n)

O(n) + O(n) = O(n^2) 

풀이소스

github.com/beomjo/algorithm-study/blob/48b8a2e9c77282ea27e84f102da90fda3299258a/BOJ/java/11052.java github.com/beomjo/algorithm-study/blob/48b8a2e9c7/BOJ/kotlin/11052.kt