카드 구매하기 2

전형적인 DP문제이다. cache[n]이 N개의 카드를 살 때 최솟값이라고 하자.

만약 10개의 카드를 최솟값으로 구매하고자 한다면

• 9개의 카드를 구매할 때의 최솟값 + 카드 1개의 비용
• 8개의 카드를 구매할 때의 최솟값 + 카드 2개의 비용
• 7개의 카드를 구매할 때의 최솟값 + 카드 3개의 비용
• ...

위와 같은 로직을 짜면 된다.

답

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	sc *bufio.Scanner
)

func init() {
	sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
}

func scanInt() int {
	sc.Scan()
	ret, _ := strconv.Atoi(sc.Text())

	return ret
}

func main() {
	N := scanInt()
	pack := make([]int, N+1)

    // 각 팩의 가격을 입력받는다.
	for ni := 1; ni <= N; ni++ {
		pack[ni] = scanInt()
	}

    // 캐시 초기화
	cache := make([]int, N+1)
	cache[0] = (1<<31) - 1
	for ci := 1; ci <= N; ci *= 2 {
		copy(cache[ci:], cache[:ci])
	}

    // 초기화
	cache[0] = 0 
	cache[1] = pack[1]
	for n := 2; n <= N; n++ {
		for i := 1; i <= n; i++ {
			cache[n] = min(cache[n], cache[n-i]+pack[i])
		}
	}

	fmt.Println(cache[N])
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}