[백준] 11052. 카드 구매하기 - 실버1

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

11052번: 카드 구매하기

 

문제 요약

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어 있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개를 구매하려고 한다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

카드팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오.

 

문제 해결 아이디어

3장의 카드를 구매하려고 한다면

- 3장이 들어 있는 카드팩을 사는 경우,

- 1장이 들어 있는 카드팩을 사고 2장의 카드를 구매하는 경우 중 최대의 비용을 지불하는 경우,

- 2장이 들어 있는 카드팩을 사고 1장의 카드를 구매하는 경우 중 최대의 비용을 지불하는 경우(결국은 1장의 카드팩을 사는 것이지만)

중 최대값을 구하면 된다.

 

4장의 카드를 구매하려고 한다면 마찬가지로

- 4장이 들어 있는 카드팩을 사는 경우,

- 1장이 들어 있는 카드팩을 사고 3장의 카드를 구매하는 경우 중 최대의 비용을 지불하는 경우,

- 2장이 들어 있는 카드팩을 사고 2장의 카드를 구매하는 경우 중 최대의 비용을 지불하는 경우,

- 3장이 들어 있는 카드팩을 사고 1장의 카드를 구매하는 경우 중 최대의 비용을 지불하는 경우

중 최대값을 구하면 된다.

 

N장의 카드를 구매하려고 한다면

- price[N]

- price[1] + dp[N-1]

- price[2] + dp[N-2]

...

- price[N-1] + dp[1]

이 나올 수 있는 모든 경우의 수가 될 것이다.

따라서 1부터 N까지 1씩 증가하는 변수 i와, 1부터 i까지 1씩 증가하는 변수 j로 이중 for문을 만들어

price[j] + dp[i-j] 값을 이전까지 구해진 dp[i]값과 비교해 최대값을 갱신해서 dp[i]에 계속해서 넣어 주면 최대 비용을 구할 수 있다. (모든 경우의 수 중 최대값을 구한다)

 

완성된 코드

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

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

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

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= N; i++) {
			price[i] = Integer.parseInt(st.nextToken());
		}

		dp[1] = price[1];

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