백준 알고리즘 11052번: 카드 구매하기

문제 정보

---

11052번: 카드 구매하기

 

핵심

---

DP를 얼마나 잘 활용할 수 있을 것인가!

오랜만에 풀어본 문제라 조금 시간이 소요된 것 같다

하지만 이러한 문제는 케이스를 나눠서 생각하다 보면 주변과의 관계가 보이는 것 같다

 

먼저 문제를 이해해 보면, P(1) P(2) 처럼 괄호 안에 들어있는 작은 숫자는 카드의 개수를 뜻한다.

(1) 은 카드 1개가 들어있는 카드팩을 뜻하며, (2)는 카드 2개가 들어있는 카드팩을 뜻한다

 

P(1)은 카드 1개가 들어있는 카드팩의 가격을 뜻한다.

P(1) = 3 이면, 카드 1개가 들어있는 카드팩의 가격은 3원 이라는 뜻이다

 

우리는 이를 적절히 조합하여 N개의 카드를 구입하려고 할 때 발생하는 최대 가격을 구하는 것이 목표이다!

DP를 왜 사용해야 하는지는 아래 풀이를 보면서 이해해 보도록 하자!

 

각각의 카드팩의 종류와 가격이 다음과 같을 때,

P[1]	P[2]	P[3]	P[4]
1	5	6	7

카드팩 1장을 구매하기 위하여 지불해야 하는 최댓값은 얼마일까?

• 카드팩 1장짜리(P[1]) 를 반드시 구매하는 경우의 수

총 1가지 경우가 존재하고, 최댓값은 1원 이다

 

아직 이해가 안갈 수 있으므로 다음 스텝으로 넘어가면

카드팩 2장을 구매하기 위하여 지불해야 하는 최댓값은?

• 카드팩 한장짜리(P[1]) 를 반드시 구매하는 경우 ( + 카드 1장을 구매)
• 카드팩 두장짜리(P[2]) 를 반드시 구매하는 경우 ( + 카드 0장을 구매)

 

우리는 반드시 모든 경우에서 최댓값을 구해야 한다.

카드팩 한장짜리(P[1]) 을 선택한다면, 남은 카드 1장을 구매하는 경우는 항상 최댓값이 되어야 하므로, 이는 아까 구했던 카드팩 1장을 구매하기 위한 최댓값 과 항상 같다.

 

카드팩 3장을 구매하기 위하여 지불해야 하는 최댓값은?

• 카드팩 한장짜리(P[1]) 를 반드시 구매하는 경우 ( + 카드 2장을 구매)
• 카드팩 두장짜리(P[2]) 를 반드시 구매하는 경우 ( + 카드 1장을 구매)
• 카드팩 세장짜리(P[3]) 를 반드시 구매하는 경우 ( + 카드 0장을 구매)

 

위 경우에서도, 앞서 말한 것과 동일하다.

카드팩 한장짜리(P[1]) 를 선택한다면, 남은 카드 2장을 구매하는 경우는 항상 최댓값이 되어야 하고, 아까 구했던 카드팩 2장을 구매하기 위해서 지불해야 하는 최댓값과 같다

카드팩 두장짜리(P[2])를 선택한다면, 남은 카드 1장을 구매하는 경우는 항상 최댓값이 되어야 하며, 아까 구했던 카드팩 1장을 구매하기 위해서 지불해야 하는 최댓값과 같다

 

우리는 "아까 구했던 카드팩 i장을 구매하기 위해서 지불해야 하는 최댓값" 을 dp[i] 라고 이름지으려고 하고, 이는 DP의 기본 베이스인 각 상태에서 가질 수 있는 최댓값을 "미리" 저장하여 해당 경우의 하위 경로를 다시 탐색하는 수고를 덜어주는 것! 이라고 할 수 있다.

 

결국, 종합해 보면 카드팩 i장을 구매하기 위해서 지불해야 하는 경우의 수들을 나열하면

• 카드팩 한장짜리(P[1]) 를 반드시 구매하고, 나머지를 구매하는 경우 (dp[i-1])
• 카드팩 두장짜리(P[2]) 를 반드시 구매하고, 나머지를 구매하는 경우 (dp[i-2])
• ...
• 카드팩 i장짜리(P[i]) 를 반드시 구매하고, 나머지를 구매하는 경우 (0)

로 나타낼 수 있을 것이며, 여기서 "나머지를 구매하는 경우" 는 반드시 최댓값을 가지는 dp[] 로 나타낼 수 있다

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

여기서 dp[i] 는 카드팩 i장을 구매하기 위해서 지불해야 하는 최댓값을 뜻하며

p[j]에서 j가 i가 될 때까지 점차 증가하고, dp[i-j] 에서 나머지 카드를 구매하는 경우(i-j) 은 하나씩 감소한다

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] p = Arrays.stream(("0 " + br.readLine()).split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] dp = new int[n+1];

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

        System.out.println(dp[n]);
    }
}

 

 

고찰

---

오랜만에 풀어봤는데, 재밌기도 하면서 살짝 아리송한 느낌이 든다

오늘부터 꾸준히 좀 풀어보려고 한다

화이팅!

 

 

Source Code on GitHub

---