[Python Algorithm] 카드 구매하기 BOJ #11052

문제

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

 

내 문제 풀이

n = int(input())
p = list(map(int, input().split()))
p.insert(0, 0)
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == 1:
            dp[i][j] = p[i] * j
        elif i > j:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(dp[i][j-i] + p[i], dp[i-1][j-i] + p[i], dp[i-1][j])

print(dp[-1][-1])

👉 DP 문제

2차원 리스트를 만들고, 매 번 가장 비싸게 살 수 있는 값을 구하여 누적했다.

대표로 1원짜리 1개 팩, 5원짜리 2개 팩으로

총 4개의 카드를 얻을 수 있는 최적의 경우를 구하는 과정을 서술했다.

 

위 예시의 경우,

1. 5원짜리 2개 팩을 두 개 구입하여 4개를 만들 수도 있고
   => dp[2][4-2] + 5
2. 5원짜리 2개 팩을 한 개 구입, 그리고 1원짜리 1개 팩을 2개 구입할 수도 있고
   => dp[1][4-2] + 5
3. 5원짜리는 구매하지 않고 1원짜리 1개 팩을 4개 구입할 수도 있다.
   => dp[1][4]

따라서 이 세 가지 경우 중 가장 큰 값을 구하여 누적하면 된다.

 

💡 피드백

전형적으로 메모이제이션과 점화식을 사용하면 되는 문제였다.

지문이 좀 복잡해서 헷갈리긴했지만 문제 유형은 무난했다.