[백준] 카드 구매하기 (★) (11052번 JAVA) / 400 - 다이나믹 프로그래밍 1

[백준] 400 - 다이나믹 프로그래밍 1 : 카드 구매하기 (!) (11052번 JAVA)

---

[접근 방법]

핵심은 동적 프로그램 인 만큼, 카드 i 개 구매의 최댓값이 저장 되고, 해당 값을 이용하여 다음 값을 구하는 것이다.

 

카드 i 개를 구매하는 경우의 수는 

카드 1개를 구매 + 카드 i - 1개를 구매,

카드 2개를 구매 + 카드 i - 2개를 구매,

카드 3개를 구매 + 카드 i - 3개를 구매 ...

하는 경우들이 존재한다.

 

카드 i개 구매의 최댓값을 저장하는 배열은 dp[] 라 하고,

카드 i개가 들어있는 카드팩의 가격을 저장하는 배열을 price[] 라 할때,

 

dp[i]  = dp[i - j] + p[j] 로 정리 할 수 있다.

※ 1 <= j <= i

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main{

    public static int[] dp;
    public static int[] price;
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];

        // 가격 저장
        price = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            price[i] = Integer.parseInt(st.nextToken());
        }

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

        bw.write(dp[N] + "\n");

        bw.flush();
        bw.close();
    }
}

 

※ [알아두기] 동적 프로그래밍의 memoization 배열 선언 자료형

// int 자료형 선언
public static int[] dp;

/*
1. 배열의 원소 값으로 null 값을 가질 수 없음.
2. 배열 원소의 초기값이 0 으로 세팅.
*/


// Integer 자료형 선언
public static Integer[] dp;

/*
1. 배열의 원소 값으로 null 값 가질 수 있음.
2. 배열 원소의 초기값 null.
*/

---

[ 2회차 풀이 (1/28) ]

[접근 방법]

1회차 풀이와 같다.

 

실행 시간 1초 = 약 2000만번 연산

N의 범위 (1 ≤ N ≤ 1,000)
O(N^2) = 1,000,000
=> 별도의 시간복잡도 고려 X

 

[JAVA 코드]

// 11052 - 카드 구매하기
import java.util.*;
import java.io.*;

class Main {
    
    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] cost = new int[N+1];
        // 카드 N개를 구입하는 금액의 최댓값
        int[] DP = new int[N+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            cost[i] = Integer.parseInt(st.nextToken());
        }

        // 1. DP를 이용한 최솟값 갱신
        for(int i=1; i<=N; i++){
            for(int j=1; j<=i; j++){
                DP[i] = Math.max(DP[i], DP[i-j] + cost[j]);
            }
        }

        // 2. 출력
        bw.write(DP[N] + "\n");
        bw.flush();
        
        bw.close();
        br.close();
    }
}


/*
실행 시간 1초 = 약 2000만번 연산

N의 범위 (1 ≤ N ≤ 1,000)
O(N^2) = 1,000,000
=> 별도의 시간복잡도 고려 X
*/

 

[Rewind]

1. 어려웠던 점

- 1회차 와 마찬가지로 점화식을 찾는 것이 어려웠다.

 

2. 알게된 점

- 방법을 알고 점화식으로 구현하는 것이 1회차 만큼 어렵지 않았다.

 

3. 해결 방안 

- 이미 한번 접했던 문제를 반복적으로 해결하며 숙달해야 한다.