[JAVA] 백준 11052번 【카드 구매하기】

---

내가 진행하고 있는 알고리즘 dp 마지막 문제이다!

 

이제 dp 문제는 쉽게 해결법이 떠오르는 것 같다.

 

역시나, dp 배열에 어떤 값을 넣어야 할지 고민하고, dp값들 사이에 관계를 맺어주는게 중요하다.

 

dp[i] 에는 주어진 카드팩을 활용해서 i장을 살때 지불하는 최대 금액을 기록할 것이다.

 

---

 

보통, 예제를 보면 규칙이 어느정도 보인다.

 

문제에서 처럼, 4장을 뽑아야 되는 상황에서

 

카드 팩 배열을 cp 라고 했을 때 

 

1장 카드 팩 = 3원 = cp[1]

2장 카드 팩 = 5원 = cp[2]

3장 카드 팩 = 15원 = cp[3]

4장 카드 팩 = 16원 = cp[4]

 

을 생각해보자.

 

dp[1] 은 1장 카드팩을 사는 경우 밖에 없으므로 dp[1] = cp[1] = 3원이다.

 

 

 

dp[2] 는 2장을 구매해야하는데,

 

1장 카드팩을 2개 사는 경우와 2장 카드팩을 1개 사는 경우가 있다.

 

즉, cp[2] 와 cp[1] + cp[1] 중 더 큰값으로 정해야 하는데

 

cp[2] = 5 > cp[1] + cp[1] = 6 이므로 

 

dp[2] = 6이 된다.

 

 

 

dp[3]은 3장 카드팩을 1개 사는 경우와

 

2장 카드팩 1개와 1장 카드팩 1개를 사는 경우와 

 

1장 카드팩 3개를 사는 경우가 있을 것이다.

 

cp[3] 과 cp[2]+cp[1] 과 cp[1]+cp[1]+cp[1] 중 가장 큰 값이 기록될 것이다.

 

cp[2]+cp[1] 과 cp[1]+cp[1]+cp[1]의 대소관계는 

 

dp[2] = max(cp[2] , cp[1] + cp[1]) 이므로 dp[2] 가 결정해주기 때문에

 

dp[2]+dp[1] 하나의 항으로 비교해도 성립한다.

 

즉 cp[3]과 dp[2]+dp[1] 중 큰 값을 dp[3]에 기록하면된다.

 

 

이제 일반화를 시켜보면

 

dp[n] = cp[n]   vs   dp[n-1] + dp[1]   vs   dp[n-2] + dp[2]   vs ······· vs   dp[1] + dp[n-1]   중 가장 큰값을 기록하면 된다.

 

참고로,,

 

dp[1] + dp[n-1] == dp[n-1] + dp[1] 이므로

 

dp[n] = Max(cp[n] , dp[n-1] +dp[1] , dp[n-2]+dp[2], ·····,dp[n/2] + dp[2/n] ) 로 비교하는 항의 갯수를 줄일 수 있다. (줄이지 않아도 정답 처리는 된다.)

 

아무튼 위와 같은 원리를 적용해서 코딩하면 된다!

 

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

public class Main {
	public static void main(String[] args) throws IOException {	
		BufferedReader br =  new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.valueOf(br.readLine());
		int [] dp = new int[N+1];
		String [] input = br.readLine().split(" ");
		int [] cardPack = new int [N+1];
		for(int i=0;i<N;i++) {
			cardPack[i+1] = Integer.valueOf(input[i]);
		}
		
//		System.out.println(Arrays.toString(cardPack));
		
		for(int i=1;i<=N;i++) {
			dp[i]=cardPack[i];
//			for(int j =1;j<=i-1;j++) { // 이렇게 해도 정답 처리는 된다.
            for(int j =1;j<=i/2;j++) {
				dp[i]=Math.max(dp[i], dp[j]+dp[i-j]);
			}
		}
//		System.out.println(Arrays.toString(dp));
		System.out.println(dp[N]);
	}
	
}

 

드디어 DP가 끝났다. 내일부터는 정렬 문제를 풀어봐야 겠다.