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

난이도

🥈 1

 

링크

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

11052번: 카드 구매하기

---

문제

---

풀이과정

해당 문제는 DP를 사용하는 문제이다.

 

DP를 사용하는 전형적인 문제로, 코테에서도 종종 볼 수 있는 문제이다.

아직 알고리즘을 잘 풀지 못하기에 점화식을 찾기 굉장히 어려웠다..

하지만 생각해보면 굉장히 쉬운 문제이다.

 

 

'N개의 카드를 갖기 위해 지불해야하는 최대금액을 출력'하는 문제이기 때문에  2중 for문을 사용하여 전부 비교해보면 된다!

예를 들어 설명하자면 dp[i] = i장의 카드를 살 경우의 최대 금액이다.

 

dp[5]인 경우 ➡️ 5장의 카드를 살 경우의 최대 금액을 구하면 되기 때문에 아래의 값들 중 최댓값이 들어가는 것이다. 

위의 예제에서 [10 9 8 7 6]의 카드 팩의 가격이 있을 때

1) 5장을 사기 위한 최대 값 + 0장 팩 값 (없음) ➡️ 6

2) 4장을 사기 위한 최대 값 + 1장 팩 값 ➡️ 50 (10+10+10+10+10+10)

3) 3장을 사기 위한 최대 값 + 2장 팩 값 ➡️ 39 (10+10+10+9)

4) 2장을 사기 위한 최대 값 + 3장 팩 값 ➡️ 28 (10+10+8)

5) 1장을 사기 위한 최대 값 + 4장 팩 값 ➡️ 17 (10+7)

 

최댓값인 50이 최대 금액이 되는 것을 알 수 있다.

 

 

위의 과정을 점화식으로 만든다면 

dp[i] = Math.max(dp[i], card[j] + dp[i-j]가 되는 것이다.

 

아래의 글의 풀이과정과 유사하므로 참고하면 좋을 것 같다!

https://amepistheo.tistory.com/11

[백준] 2293 : 동전 1 (JAVA)

---

전체 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] card = new int[N + 1];
        int[] dp = new int[N + 1];

        st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) {
            card[i] = Integer.parseInt(st.nextToken());
        }

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

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

 

결과