백준 [11052]: 카드 구매하기

📌 백준 [11052]: 카드 구매하기

🔗 문제 링크

---

문제 설명 📄

카드 팩의 개수 n이 주어지고, 각 팩의 가격이 주어진다.
n개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하시오.

---

문제 접근 방식 💡

• 동적 프로그래밍(DP)을 사용하여 최대 구매 비용을 계산.
• dp[i]를 i개의 카드를 구매할 때의 최대 비용으로 정의.
• 점화식:
  • dp[i] = max(dp[i], dp[i-j] + cards[j])
  • 여기서 j는 선택한 카드 팩의 개수를 의미.
• 초기값:
  • dp[0] = 0 (카드를 구매하지 않은 경우).

---

Solution 💻

n = int(input())

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

dp = [0] * (n + 1)

for i in range(1, n + 1):
    for j in range(1, i + 1):
        dp[i] = max(dp[i], dp[i - j] + cards[j])

print(dp[n])

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n^2)
  • 이중 반복문을 통해 모든 카드 팩 조합을 고려.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • dp 배열이 n+1 크기로 사용됨.

---

리팩토링 🛠️

n = int(input())

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

dp = [0] * (n + 1)

for i in range(1, n + 1):
    dp[i] = max(dp[i - j] + cards[j] for j in range(1, i + 1))

print(dp[n])

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n^2)
  • 리스트 컴프리헨션을 활용하여 코드 간결화.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • dp 배열의 크기만큼 메모리 사용.