[백준 JAVA] 11052번 풀이 - 카드 구매하기 (+16194번)

 

생각의 방향

이전에 풀었던 1,2,3 더하기 문제에서 힌트를 얻었다. 

카드를 1개 구매하는 상황부터 최대값을 구할 수 있는 경우의 수를 카운트 했다. 

p[1]=1
p[2]=5
p[3]=6
p[4]=7

- dp[1] : 카드가 1일 때의 최대값은 p[1] 만 가능하다. 

dp[1] = p[1] = 1

 

- dp[2] : 카드가 2일 때의 최대값을 구하는 경우의 수는 (1 * 2) , (2) 이다. 

dp[2] = p[2] + dp[0] = 5 + 0 = 5

(1 * 2)의 경우, dp[1] 에서 p[1]  카드 하나를 더 사면 된다. 

dp[2] = dp[1] + p[1] = 1 + 1 = 2  

dp[2] 의 최대값은 5이다.

 

- dp[3] : 카드가 3일 때의 최대값을 구하는 경우의 수는 (1 * 3), (2 * 1), (3) 으로 3가지이다. 

dp[3] = p[3] + dp[0] = 6 + 0 = 6

이번에는 dp[2] 에서 p[1] 카드를 하나 더 사는 방법이다. 

dp[3] = dp[2] + p[1] = 5 + 1 = 6

마지막으로 dp[1] 에서 카드 2개를 더 살 수 있다. 

dp[3] = dp[1] + p[2] = 1 + 5 = 6

dp[3] 의 결과는 3가지 경우 모두 최대값이 6이다. 

 

- dp[4] : 카드가 4일 때의 최대값을 구하는 경우의 수는 (4), (2 * 2), (3 * 1), (1 * 3) 으로 4가지 이다. 

dp[4] : p[4] + dp[0] = 7 + 0 = 7

(2 * 2)의 경우, dp[2] 에 p[2] 카드를 산다. 

dp[4] = dp[2] + p[2] = 5 + 5 = 10

(3 * 1)의 경우 dp[3] 에 p[1] 카드를 산다. 

dp[4] = dp[3] + p[1] = 6 + 1 = 7

(1 * 3)도 마찬가지로 dp[1] 에 p[3] 카드를 사준다.

dp[4]  = dp[1] + p[3] = 1 + 6 = 7

dp[4] 의 최대값은 dp[4] = dp[2] + p[2] = 5 + 5 = 10 이다.

 

dp[4] 구하는 방법 
dp[4] = dp[0] + p[4]
dp[4] = dp[1] + p[3]
dp[4] = dp[2] + p[2] 
dp[4] = dp[3] + p[1]

 

위에 식을 토대로, dp[i-j] + p[j] 형태를 도출할 수 있다. 

해당 형태의 식을 가지고 구한 최대값을 이전에 구한 dp[i] 와 비교하여, 최대값만 저장하면 된다!

 

코드

package baekjoon;

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

public class _11052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); //횟수

        int [] p = new int[1001];
        int [] dp = new int[1001];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++){
            p[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], dp[i-j] + p[j]);
            }
        }

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

    }
}

 

유사한 문제 16194번 - 카드 구매하기 2

package quiz;

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

/**
 * 카드 구매하기 2
 * 이번에는 돈을 최소로!! 지불해서 카드 n개를 구매한다.
 */
public class _16194 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int [] p = new int[1001];
        int [] dp = new int[1001];

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

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

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

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