문제
요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.
PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.
- 전설카드
- 레드카드
- 오렌지카드
- 퍼플카드
- 블루카드
- 청록카드
- 그린카드
- 그레이카드
카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.
민규는 지난주에 너무 많은 돈을 써 버렸다. 그래서 오늘은 돈을 최소로 지불해서 카드 N개를 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.
예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최솟값은 4원이다. 1개 들어있는 카드팩을 4번 사면 된다.
P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 2개 들어있는 카드팩을 2번 사면 4원이고, 이 경우가 민규가 지불해야 하는 금액의 최솟값이다.
카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.
풀이
-
테이블 정의
dp[i] = 카드를 i개 샀을 때 최소값 -
점화식구하기
j는 i의 이전 값들
dp[i] = min(dp[i], dp[i-j] + cards[j])예를들어 하나씩 살펴보자
i가 2일 때
for문이 시작되면 dp[2]에는 cards[2]값이 대입되고 j순회를 시작한다. j는 i+1까지 순회하기때문에 2까지 순회할 것이다.j가 1일 때
dp[2] = min(dp[2], d[2-1] + cards[1])
카드를 한 개 살 때 최솟값과 카드 한개의 값을 더해주고 있다.j가 2일 때
dp[2] = min(dp[2], dp[2-2] + cards[2])
카드를 두개 살 때 가격인 cards[2]의 값과 이전에 저장된 최솟값과 비교하여 최솟값 연산을 해준다.이렇게 i-j개 살 때의 최솟값에 j개 묶음의 카드를 사는 가격을 더한 값과 이전값 연산을 통해 최솟값을 구할 수 있다.
-
초기값 설정
카드를 0개 고르면 0이므로 dp[0] = 0
그리고 1개 고르는 값의 최솟값도 1개를 사는 가격과 같기 때문에 dp[1] = cards[1]
N = int(input())
cards = [0] + list(map(int, input().split()))
INF= int(10e9)
dp = [INF] * (N+1)
dp[0] = 0
dp[1] = cards[1]
for i in range(2, N+1):
for j in range(1, i+1):
dp[i] = min(dp[i] , dp[i-j] + cards[j])
print(dp[N])피드백
dp 테이블, 점화식 도출도 잘 해놓고 초기값 설정을 안해서 이래저래 둘러갔다.
풀기로 했던 순서대로 잘 지켜서 풀자
