코딩테스트 스터디-11052 카드구매

ACMICPC 11052 카드 구매하기

백붕이는 카드를 사려고 하는데, 카드 N개를 사는 데 최대한 돈을 많이 쓰려고 한다.
카드가 i개 포함된 카드팩의 가격을 Pi라 할 때,
카드팩이 총 4가지 종류가 있고 P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에
백붕이가 카드 4개를 갖기 위해 지불해야 하는 금액의 최대값은 10원이다.
2개 들어있는 카드팩을 2번 사면 되기 때문.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해
백붕이가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오.
N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은
불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야
한다.

첫째 줄에 백붕이가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)
둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

설명

아아…본인이 가장 싫어하는 DP 문제이다.
지금까지 거친 코딩테스트에 DP문제가 없었던 것이 정말 다행일 따름이다.

아무튼 DP의 핵심은 공식 세우기이다.
N이 증가할 때 그 전것들과 어떤 관계가 있는지만 나오면 풀이는 간단…하지 않고
그걸 또 코드로 구현하는 게 죽을 지경이다.

#1개 2개 3개 4개
#1   5   6   7

#4개를 살 때 최대값은!

아무튼 위 경우에서 일단 수기로 N을 증가시킬 때의 경우를 따 보면

• 1개: 1(P1) - 최대값은 1이므로 P2=1
• 2개: 2(P1+P1), 5(P2) - 최대값은 5이므로 P2=5
• 3개: 3(P1+P1+P1), 6(P1+P2), 6(P3) - 최대값은 6이므로 P3=6
• 4개: 4(P1+P1+P1+P1), 7(P1+P1+P2), 7(P1+P3), 10(P2+P2), 7(P4) …

이런 식으로 각각 최대금액(n): 최대값(
최대금액(n)+최대금액(0),
최대금액(n-1)+최대금액(1),
최대금액(n-2)+최대금액(2),…)
순으로 진행해야 한다.

정답

아래는 파이썬으로 작성한 코드~

n = int(input())
kards = list(map(int,input().split(" ")))

# 카드 개수별 최대 금액이 담길 배열: 0장부터 시작
ee = [0] + kards


def solution(n):
    # 위의 공식을 코드로 재현
    for i in range(1,n+1):
        for j in range(0,i):
            ee[i] = max(ee[i],ee[j]+ee[i-j])
    return max(ee)

print(solution(n))       

• n이 1일 경우 solution:
  • i는 1만, j는 0
  • 따라서 ee[1]은 max(ee[1],ee[0]+ee[1])로 1
• n이 2일 경우:
  • i가 2일 때 j는 0,1
  • 따라서 ee[2]는 max(ee[2],ee[0]+ee[2])->max(ee[2],ee[1]+ee[1]) 순으로 진행
• n이 3일 경우:
  • i가 3일 때 j는 0,1,2
  • 따라서 ee[3]은 max(ee[3],ee[0]+ee[3])->max(ee[3],ee[1]+ee[2])->max(ee[3],ee[2]+ee[1]) 순으로 진행
• 이미 이전 단계에서 각 개수의 최대값을 구했으므로 그 다음의 최대값은 각 개수들을 조합하면서 최대값을 구하는 방식

후기

DP는 그 구현의 악랄함? 때문에 고난이도 문제로 자주 출제된다.
솔직히 만들어놓고 저게 어떤 원리인지 확실히 깨닫지 못하겠다…