[코딩테스트/백준 알고리즘] 11052번 : 카드 구매하기 (자바, Java 풀이)

문제

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

11052번: 카드 구매하기

---

문제 설명

---

문제 풀이

카드 1장을 가장 비싸게 사는 방법

- 1장 짜리 카드팩을 구매하는 비용

 

 

카드 2장을 가장 비싸게 사는 방법

- 2장 짜리 카드팩을 구매하는 비용

- 1장 짜리 카드팩을 구매하는 비용과 카드 1장을 가장 비싸게 사는 비용의 합

중 비싼 것을 선택

 

 

카드 3장을 가장 비싸게 사는 방법

- 3장 짜리 카드팩 구매하는 비용

- 1장 짜리 카드팩을 구매하는 비용과 카드 2장을 가장 비싸게 사는 비용의 합

- 2장 짜리 카드팩을 구매하는 비용과 카드 1장을 가장 비싸게 사는 비용의 합

중 가장 비싼 것을 선택

 

 

카드 4장을 가장 비싸게 사는 방법

- 4장 짜리 카드팩을 구매하는 비용

- 1장 짜리 카드팩을 구매하는 비용과 카드 3장을 가장 비싸게 사는 비용의 합

- 2장 짜리 카드팩을 구매하는 비용과 카드 2장을 가장 비싸게 사는 비용의 합

- 3장 짜리 카드팩을 구매하는 비용과 카드 1장을 가장 비싸게 사는 비용의 합

중 가장 비싼 것을 선택

 

 

카드 n장을 가장 비싸게 사는 방법

- n장짜리  카드팩을 구매하는 비용

- 1장 짜리 카드팩을 구매하는 비용과 카드 (n - 1)장을 가장 비싸게 사는 비용의 합

- 2장 짜리 카드팩을 구매하는 비용과 카드 (n - 2)장을 가장 비싸게 사는 비용의 합

.

.

.

- (n - 1)장 짜리 카드팩을 구매하는 비용과 카드 1장을 가장 비싸게 사는 비용의 합

중 가장 비싼 것을 선택

 

 

이런 식으로 Bottom-up 방식을 사용하여 문제를 해결했다.

---

코드

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] price = new int[n + 1];
        int[] memo = new int[n + 1];
        
        for(int i = 1; i <= n; i++) {
            price[i] = sc.nextInt();
        }
        memo[1] = price[1];
        
        for(int i = 2; i <= n; i++) {
            memo[i] = price[i];
            for(int j = 1; j <= i; j++) {
                int tmp = memo[j] + memo[i - j];
                memo[i] = memo[i] > tmp ? memo[i] : tmp;
            }
        }
        System.out.println(memo[n]);
    }
}

---

총평

DP 문제는 어떻게 설명해야 명확하게 설명할 수 있을지 풀이를 쓰기가 어려운 거 같다.