[Java] 백준 11052 : 카드 구매하기

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

11052번: 카드 구매하기

 

---

- 카드 i개가 들어 있는 카드팩 각 가격 price[]

- 카드 N개를 구매하기 위한 최대금액 dp[]

 

아래처럼 진행이 되는데 여기서 규칙을 찾으면 된다. 

 dp[0]=0,

1) 카드 한 장을 살 때 필요한 금액

dp[1]=price[1] =dp[0] + price[1]

2) 카드 두장을 살 때 필요한 금액

dp[2]=price[2] =dp[0] + price[2]

dp[2]=price[1]*2 = dp[1]*2 = dp[1] + price[1]

3) 카드 세장을 살 때 필요한 금액

dp[3]=price[3] =dp[0] + price[3]

dp[3]=price[2]+price[1] = dp[1] + price[2] = dp[2] + price[1]

dp[3]=price[1]*3 

 

정리해 보면 

i=3일 때, 

dp[i] = dp[i-3] + price[i]

dp[i] = dp[i-2] + price[i-2]

dp[i] = dp[i-1] + price[i-3]

 

1개 들었을 때의 금액부터 계산해서 최댓값을 비교해 나가면 된다. 

 

import java.util.*;


public class Main {
	
	static int N;
	static int [] dp,price;
	public static void main(String[] args){
		Scanner sc= new Scanner(System.in);
		N=sc.nextInt();
		price = new int[N+1];
		dp = new int[N+1];
		
		for(int i=1;i<=N;i++) {
			price[i]=sc.nextInt();
		}
		
		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]);
            }
        }
		
		System.out.println(dp[N]);
		
	}// main()
	
	 
}// class Main