백준: 16194 카드 구매하기 2

문제

16194번: 카드 구매하기 2

 

문제 풀이

 카드 구매하기에서는 구매하고자 하는 카드를 최대값으로 구매하는 문제였다. 이와 달리 카드 구매하기 2는 가장 최소 값으로 카드를 구매할 경우에 발생하는 금액을 반환하는 문제이다. 카드 구매하기와 동일한 방법으로 풀며, 약간의 코드를 수정하면 이 문제도 쉽게 풀 수 있다.

 

코드

if __name__ == '__main__':
    N = int(input())
    card = [0] + list(map(int, input().split()))

    memo = [0] * (N + 1)
    memo[1], memo[2] = card[1], min(card[2], card[1] * 2)

    for i in range(3, N + 1):
        memo[i] = card[i]
        for j in range(1, i // 2 + 1):
            memo[i] = min(memo[i], memo[j] + memo[i - j])
    print(memo[N])

 최대값을 찾는 것이 아닌, 최솟값을 찾아야 하므로 max를 min으로 변경하면 된다.