[Python] 11052. 카드 구매하기

n = int(input())
cards = [0] + list(map(int, input().split()))
dp = [0 for _ in range(n+1)]    # 각 자리에는 카드 i개를 구매하는 최대 가격이 저장됨

for i in range(1, n+1):
   for j in range(1, i+1): # i가 4면 (3, 1), (2, 2), (1, 3)일 때를 보는것
       dp[i] = max(dp[i-j] + cards[j], dp[i]) # i개 구매할때의 최대 가격 갱신

print(dp[n])

 

풀이 포인트

• dp 리스트의 자리 i에는 카드 i개를 구매하는 최대 가격이 저장된다.
• 이중 for문을 돌면서 카드 i개를 구매하는 경우, j가 1부터 돌면서 dp[i-j] + cards[j] 의 값들 중, 최댓값을 dp[i]에 저장하게 된다.
  • dp[i-j] + cards[j]의 예
    • i = 4인 경우, dp[3] + cards[1], dp[2] + cards[2], dp[1] + cards[3] 중 최댓값을 dp[4]에 저장한다. 

 

처음 접근한 방법 

n = int(input())
cards = list(map(int, input().split()))
answer = 0

for i in range(1, n+1):
    if n % i:  # i개로 n개의 카드를 채울 수 없을 때
        temp = cards[i-1] * (n//i) + cards[(n%i)-1]   # i개의 카드팩으로 n을 채우고, 남는건 그만큼에 해당하는 개수의 카드팩 사
    else:   # i개로 n개의 카드 다 채울 때
        temp = cards[i-1] * (n//i)  # i개 들어있는 카드팩 n//i개만큼 사기

    answer = max(answer, temp)  # 금액의 최댓값 갱신

print(answer)

여기서 오류는 n이 i로 나누어 떨어질 수 없다면, 일단 i개 카드가 들어있는 카드팩을 n//i 개 사고 나머지(n%i)는 거기에 맞는 카드팩을 불러오는 형식이었는데,
여기서 cards[(n%i)-1]이 되면 안되는 이유는, 만약 n%i가 3이라면 cards[3]보다 cards[1]*3의 값이 더 클 수 있기 때문이다.

따라서 dp[(n%i)-1]가 되어야 하는데 거기 자리에 최댓값이 있어야 하기 때문에 점화식을 써야 했다. 

그래서 생각하다가 코드를 다 지우고 맨 위의 코드를 짜게 되었다.