b11052. 카드 구매하기

 

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

 

 

 

✨ 자바로 푸는 카드 구매하기 문제 풀이

 

---

 

📌 문제 개요

 

• N개의 카드를 구매해야 할 때, 각 카드팩은 카드 개수와 가격이 다르다.
• 카드 N개를 구매하는 최대 금액을 구해야 한다.
• 전형적인 완전 탐색 기반의 DP 최적화 문제.

 

---

 

💡 예제 입력

4  
1 5 6 7

설명:

카드 1개짜리 팩은 1원, 2개짜리 팩은 5원, …

4개를 구매할 때 최대 금액을 구하는 문제.

 

---

 

🛠 알고리즘 접근 방식

 

1. dp[i]는 카드 i개를 구매할 수 있는 최대 비용을 의미.
2. i장을 구매하려면:
   • j장을 먼저 사고, 나머지 i-j장을 다시 구입할 수 있다.
   • 즉, dp[i] = max(dp[i], dp[i-j] + price[j])
3.  
4. 이때 모든 j에 대해 반복하면서 최대값 갱신.

 

---

 

✅ 핵심 아이디어

 

• 점화식:

dp[i] = max(dp[i], dp[i - j] + price[j])

 

•  
• 완전 탐색하면서 dp 배열을 갱신.

 

---

 

🧾 코드 해설

 

 

🎯 입력 및 초기화

int N = Integer.parseInt(br.readLine());
int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[] dp = new int[N+1];
for (int i = 1; i <= N; i++) {
    dp[i] = arr[i-1];
}

 

• arr[i-1]은 i장을 사는 카드팩 가격.
• dp[i] = arr[i-1]은 해당 카드팩을 단독으로 구매했을 경우를 초기값으로 세팅.

 

---

 

🔁 점화식 구현

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= i; j++) {
        dp[i] = Math.max(dp[i], dp[i-j] + dp[j]);
    }
}

 

• i장을 만들기 위해 j장 + (i-j)장으로 나누어보며 최대값 갱신.

 

---

 

✅ 핵심 포인트 정리

 

• 카드 구매를 나누어 계산해야 하는 부분 문제 최적화 유형.
• dp[i] = max(dp[i], dp[i-j] + dp[j])을 잘 이해하는 것이 핵심.
• 전형적인 1차원 DP 누적 최적화 문제.