카드 구매하기

최근 SW 역량 테스트 준비 - 기초 : 다이나믹 프로그래밍 부분의 문제들을 쭉 풀고있다. 비교적 쉬운 DP문제들이지만, 정말 기초가 다져지는 느낌이다.

문제분석

카드 구매하기, 카드 구매하기 2 이렇게 비슷한 문제가 두문제 있다. 두문제 모두 풀었지만, 최대 최소 외에는 상당 부분이 동일함으로 ‘카드 구매하기’만 포스팅 할 계획이다.

카드팩의 가격이 차례대로 주어지고, 카드팩에 들어있는 카드의 개수는 순서대로 1,2,3, … 이다. N개의 카드를 살 때, 지불하는 금액의 최대값을 구하면 된다.

Knapsack 문제와 상당히 비슷하다는 것을 알 수 있다.

Knapsack 문제에서 물건의 가치와 무게가, 이 문제에서는 카드팩의 가격과 카드팩안에 들어있는 카드 개수라고 할 수 있다.

  • 물건의 가치 » 카드팩의 가격
  • 물건의 무게 » 카드팩안에 들어있는 카드 개수

Knapsack 문제와의 다른 점은 Knapsack 문제에서는 동일 물건을 최대 한개 가방에 담을 수 있었지만, 이 문제에서는 카드팩을 몇 개 사는지에 제한이 없다는 것이다.

4
3 5 15 16

위의 예제를 통해 알아보자.

Crepe

  • 먼저 N+1의 길이를 가지는 DP리스트를 만들어주자. 각각의 칸에는 n개의 카드를 구매할 때 지불하는 가격의 최대값이 들어갈 것이다.

  • 카드팩에 들어있는 카드의 개수가 작은것 부터 탐색해 나간다.

  • 카드를 1개 구매할 때, 가격의 최대값은 3, 2개 구매할 때 6 … 4개 구매할 때 12임을 알 수 있다. (3*n)

  • 카드의 개수가 2개인 카드팩의 가격은 5이다. 카드를 2개 구매할 때, 5보다 기존에 들어있는 값이 큼으로, DP[2]=6이다.
  • 카드를 세개 구매할 때도, 5+3보다 기존에 들어있는 값이 크기 때문에 DP[3]=9이다.

  • 카드를 네개 구매할 때는 2개짜리 카드팩을 두개 구매할 경우, 1개 구매할 경우, 0개 구매할 경우 이렇게 세가지 케이스를 비교한다. 그래도 여전히 기존의 값이 큼으로 DP[4]=12이다.

  • 카드의 개수가 3개인 카드팩과 4개인 카드팩에 대해서도 동일한 과정을 거친다.

이와 같은 방법으로 카드를 N개 구매할 때 지불할 수 있는 금액의 최대값을 구할 수 있다. Knapsack 문제에 물건을 중복해서 넣는 경우까지 고려해서 푼다고 생각하면 수월할 것이다.

CODE

import sys
read=sys.stdin.readline

n=int(read())
card=[0]+list(map(int,read().split()))

dp=list(0 for _ in range(n+1))

for i in range(1,n+1):#카드팩안에 들어있는 카드의 개수 = i
    for j in range(n,i-1,-1):
        for k in range(1,1+j//i):#i개의 카드가 들어있는 카드팩을 k 개 사는 경우
            dp[j]=max(dp[j],dp[j-i*k]+card[i]*k)
print(dp[-1])


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]