백준(BaekJoon) 11052번 : 카드 구매하기 - python 풀이

❓11052번 : 카드 구매하기

📈 문제 요약

구매하려고 하는 카드 개수 N이 주어질 때 카드를 한 번에 n(1 ≤ n ≤ N)장 사는 가격이 주어지는 경우 카드 N장을 가장 비싸게 주고 사는 가격을 구하면 되는 문제

🤨 접근법

카드를 한 번에 사는 개수가 뒤죽 박죽이었으면 정말 어려운 문제였겠지만! 친절하게도 카드를 한번에 1장 부터 N장까지 사는 가격이 순서대로 주어졌다.

전체 문제인 카드 N장을 가장 비싸게 주는 가격을 구하는 문제에서 부분 문제를 카드 i(1 ≤ i ≤ N)장을 가장 비싸게 주는 가격을 구하는 문제로 정의하여 DP로 접근하였다.

• i=1인 경우
  • 1장을 한 번에 사는 경우
• i=2인 경우
  • 1장씩 1번 사는 경우 + 1장씩 1번 사는 경우, 2장씩 1번 사는 경우
• i = 3
  • 1장씩 1번 사는 경우 + 2장 사는 경우, 2장씩 1번 사는 경우 + 1장 사는 경우, 3장씩 1번 사는 경우

…

• i = N
  • 1장씩 N번, 2장씩 1번 + N-2장 사는 경우, 3장씩 1번 + N-3장 사는 경우 , …, N장씩 1번 사는 경우

이렇게 경우의 수를 도출할 수 있고 각 i에서의 모든 경우의 수에서 가격이 가장 높은 경우의 수를 선택하면 된다.

즉, 점화식을 다음과 같이 정할 수 있다.

$dp[i] = max(cards[1]+dp[i-1], cards[2]+dp[i-2], ..., cards[i])$

물론 i=1부터 Tabulation을 진행하면서 값을 구해야 정상적으로 조건에 맞는 값을 구해낼 수 있다.

🔡코드

import sys

input = sys.stdin.readline

N = int(input())
cards = [0]+list(map(int, input().rstrip().split()))
dp = [0, cards[1]]

for i in range(2, N+1):
    tmp = [cards[i]]
    for j in range(1, i):
        tmp.append(dp[i-j]+cards[j])
    dp.append(max(tmp))

print(dp[N])

i=1인 경우는 1장씩 1번 사는 경우밖에 존재하지 않기 때문에 기저로써 dp 배열에 넣고 시작하였다.

i장을 사는 각각의 모든 경우의 수의 최댓값을 구하기 위해 별도의 tmp배열을 활용했다. 일단 값을 넣어주고 max로 비교해가며 업데이트 하는 방법으로도 풀이가 가능할 것이다! 하지만 max연산을 각 한 번씩만 할 수 있다는 점에서 이렇게 코드를 작성하는 것이 효율적일 것 같다!

🎉 빰빠라밤

진짜 거의 처음으로 내가 스스로 점화식을 도출해서 풀이한 문제!