백준 11052번 <카드 구매하기>

백준 알고리즘 11052번

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

11052번: 카드 구매하기

---

11052번

민규는 같은 n개를 사도 비싸게 사면 좋은 카드가 더 많이 들었을 거라고 생각한다.

주어진 카드 개수를 제일 비싸게 살 수 있을 때 얼마가 드는지 구하여라.

 

입력으로 첫 줄에 카드 팩의 개수 n이 들어온다. 그리고 그 다음 줄에 n개의 정수가 들어온다.

(카드 팩은 각각 1개, 2개, 3개 ... n개로 구성되어 있고 들어온 정수는 각 카드 팩의 금액이다.)

만약 카드의 개수가 n이고, 1 2 3이 들어온다면 1은 카드 1개를 사는데 금액은 1이고, 카드 2개를 사는데 금액은 2, 카드 3개를 사는데 금액은 3이라는 의미이다.

 

출력으로 카드 n개를 살 때, 가장 비싸게 사는 금액을 출력하면 된다.

---

문제 해결

다이나믹 프로그래밍으로 풀 수 있다.

 

메모제이션하는 테이블을 dp라고 정의했다.

dp[i]는 i개의 카드를 사는데 드는 금액의 최댓값이다.

(모든 배열은 1 indexed로 맞추었다.)

 

dp[1]은 cards[1]이다.

dp[i]는 dp[1] * i와 dp[1] + dp[i-1], dp[2][ + dp[i-2] ... , cards[i] 중 큰 값이다.

굵은 글씨로 표시한 부분은 앞의 index가 뒤의 index보다 작을 때만 진행한다.

---

코드

package bj11052;

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

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[] cards = new int[n + 1];
		cards[0] = 0;
		String[] inArr = new String[n];
		inArr = br.readLine().split(" ");
		for (int i = 1; i < n + 1; i++) {
			cards[i] = Integer.parseInt(inArr[i - 1]);
		}
		int[] dp = new int[n + 1];
		dp[0] = cards[0];
		dp[1] = cards[1];

		for (int i = 2; i < n + 1; i++) {
			int temp = cards[1] * i;
			temp = Math.max(temp, cards[i]);
			for (int j = 1; j < i; j++) {
				int a = i - j;
				if (a < j) {
					break;
				}
				temp = Math.max(temp, dp[j] + dp[a]);
			}
			dp[i] = temp;
		}

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

	}

}

코드(23.01.04)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;

/*
* 다이나믹 프로그래밍으로 풀 수 있다.
* dp[i] : i개의 카드를 뽑는데 드는 최대 금액
* dp[i] : max(dp[1] + dp[i-1], dp[2] + dp[i-2], ... , dp[i/2] + dp[i-i/2], prices[i])
*
* N의 최대 수가 1000이기 때문에
* 최대 금액은 1,000 * 10,000 = 10,000,000 이기 때문에 int 형 사용
*
* dp[1000]을 구하기 위해서
* 500의 연산 필요
* dp 배열의 값을 구할 때 모두 500의 연산을 한다고 가정하면
* 500 * 1,000 = 500,000의 연산 필요.
* */
public class BOJ11052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());       // N : 카드의 개수
        String[] inArr = br.readLine().split(" ");
        int[] prices = new int[N+1];    // prices[i] : i개의 카드가 들은 카드팩의 가격
        for(int i = 0; i < N; i++){
            prices[i+1] = Integer.parseInt(inArr[i]);
        }

        int[] dp = new int[N+1];    // dp[i] : i개의 카드를 뽑는데 드는 최대 금액
        dp[1] = prices[1];

        for(int i = 2; i <= N; i++){
            for(int j = 1; j <= i / 2; j++){
                dp[i] = Math.max(dp[i], dp[j] + dp[i-j]);
            }
            dp[i] = Math.max(dp[i], prices[i]);
        }
        System.out.println(dp[N]);
    }
}
/*
5
1 10 1 1 1
21
-----------------
6
3 4 2 8 4 20
20
-----------------
6
3 4 2 8 4 10
18

* */

---

결과

---