[백준 16194번] 카드 구매하기 2

n = int(input())
data = list(map(int,input().split()))

p_count = len(data)

dp = [[0]*(n+1) for _ in range(p_count+1)]

for i in range(1,n+1):
    dp[1][i] = data[0]*i

for i in range(2,p_count+1):
    for j in range(1,n+1):
        if i > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j], data[i-1] + dp[i][j-i])

print(dp[p_count][n])

이번 문제는 P1부터 PN까지 카드가 N개가 포함된 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 지불해야 하는 금액의 최솟값을 구하는 문제이다.

 

이 문제는 이전에 풀이했던 카드 구매하기 1 문제를 응용한 문제인데, 이번에는 2차원 DP 테이블을 '각 카드의 사용 여부'를 행으로, '구매하고자 하는 카드의 개수'를 열로 지정하여 생성하였다.

0	5	10	15	20
0
0
0

위 표는 초기값을 설정해준 DP 테이블의 모습이다. 첫번째 행은 카드의 개수가 1개인 카드팩밖에 존재하지 않으므로 P1(1개 카드팩의 가격)에 카드의 개수를 곱해주면 된다.

0	5	10	15	20
0	5	2	7	4
0	5	2	7	4
0	5	2	7	4

그 후에 현재 구매하고자 하는 카드의 개수를 현재 행에 해당하는 카드를 사용하지 않고 구매하는 방법(dp[i-1][j])과 현재 행에 해당하는 카드를 사용하여 구매하는 방법(data[i-1] + dp[i][j-i])을 비교하여 min함수를 사용해 더 작은 값을 DP 테이블에 저장해주었다.

(i > j , 즉 현재 카드팩의 카드 개수가 구매하고자 하는 카드의 개수보다 많은 경우에는 현재 카드를 사용하지 못하기 때문에 현재 카드를 사용하지 않고 만들 수 있는 경우의 수인 DP[i-1][j]를 그대로 가져와주었다.)

 

이 방식으로 DP 테이블을 채워나가면서 구매하고자 하는 카드의 개수 N까지 Bottom-Up 기법으로 풀이하여 문제를 해결할 수 있었다 :)

 

계산한 정보나 문제를 별도의 자료구조에 저장하여 중복 연산을 줄이는 방식으로 프로그램 수행 속도를 높이는 DP 알고리즘을 다시 한번 Remind할 수 있었던 좋은 문제였다.