백준 11052 카드구매하기 파이썬

백준 11052 카드구매하기 풀이

접근방식

1. 금액의 최댓값을 저장할 dp리스트를 생성합니다.
2. 2개의 카드를 구매하는 경우는, 1개의 카드를 2개 구매하거나, 2개짜리
   카드팩을 구매하는 경우 두가지로 나눌 수 있습니다.
3. 3개의 카드의 경우, 1개의 카드팩 3개, 2개의 카드팩 + 1개의 카드팩, 3개의 카드팩 1개
   구매하는 3가지 경우가 있습니다.
4. 이처럼, 카드를 구매할 수 있는 경우를 max 함수를 이용해서 최댓값을 구해야 합니다.
5. 예를 들어, dp[3] = max(dp[3], dp[2] + dp[1])입니다.
6. 이를 해석하면, 3개의 카드팩 1개를 구매하거나, 2개 카드팩 1개와 1개 카드팩 1개를 구매하는
   경우 중 최댓값을 구하는 것입니다.

오답코드

import sys
input = lambda: sys.stdin.readline().rstrip()

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

max_val = -int(1e9)

for i in range(1, n+1):
    max_val = max(max_val, card[i] * (n//i) + card[(n%i)])
    
print(max_val)

기존의 오답은 for문을 돌려서 몫과 나머지 만큼 해당하는 카드팩을
구매하는 경우를 고려했지만, 예를 들어, 카드 2개가 남을 경우,
이를 1개의 카드팩 2개로 구매할 것인지, 2개 카드팩 1개로 구매할 것인지 등의
경우는 해결할 수 없다는 점에서 한계가 있었습니다.

정답코드

import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

dp[1] = card[1]
# 2개짜리 카드팩 1개 vs. 1개짜리 카드팩 2개
dp[2] = max(card[2], card[1] * 2)

for i in range(3, n+1):
  # 기본적으로 자기 자신의 값을 가집니다.
    dp[i] = card[i]
    for j in range(1, i//2 + 1):
        dp[i]= max(dp[i], dp[j]+dp[i-j])

print(dp[n])

해당 문제는 실버 1레벨의 다이나믹 프로그래밍 문제였습니다.

이 문제에서는 2중 for문을 돌릴 때, range 범위를 1부터 (i//2 + 1)로 지정해서

나올 수 있는 경우를 모두 고려해주도록 하는 부분이 핵심이라고 생각합니다.

알고리즘도 모든 것과 마찬가지로 꾸준한 연습과 이해를 바탕으로 실력이 향상합니다.
Just do it & Keep steady