자바(백준) 11052 카드 구매하기

오답 노트 & 새로 알게 된 점

이 문제를 풀려고 한 5~6시간 쓴 것 같다. 처음에 dp공부하는 것은 너무나 많은 생각과 시간을 투자한다. 하지만 중요한 부분이니 견디고 견뎌서 dp를 정복해야한다,, 그리고 문제 풀이에 매우 큰 도움을 주신 류호석님께 너무 감사한다,,

 

첫 번째, 문제 접근을 잘못하여 파티션을 제대로 나누지 못했다.

류호석님 dp강의를 보면 dp를 풀기 위해서는 파티션을 나눠야 한다.

하지만 문제에서 1+2+2, 2+1+2, 2+2+1은 항상 같은 값으로 나오기 때문에 처음 나는 중복된 것을 뺐다. 그래서 파티션을 나눠서 공통점을 찾으려는 과정에서 어려움을 겪게 되고, 찾지 못하게 된다. 

 

그래서 질문을 하게 되었고, 위의 중복된 값을 같이 써야 한다고 말씀해주셨다. 왜냐하면 빼놓고 쓰게 되면, 파티션을 나누기가 어렵다고 하셨다. 그래서 모든 경우의 수를 쓰면 아래의 사진과 같게 된다.

 

 

그리고 나서 파티션을 하게 되면 아래의 사진과 같아진다.

끝이 1일 경우, 2일 경우 등 나뉘게 된다.

 

 

그렇다면 여기서 생각을 더 해보자.

해당 예는 N = 5일 때이다.

 

i-1 파티션을 보면 뒤의 1을 빼면 N = 4일 때와 똑같다. 즉 이 말은, 전에 풀었던 문제와 비슷하게, 최댓값을 구하기 위해서는 어떤 수를 더하든 간에 최댓값에서 더해야 최댓값이 나오게 된다. 그래서 N = 4일 때 경우의 수 중에 최댓값을 뽑아 arr[1]을 더해주면 P1 한 장 + (총카드의 4장 되기 위한 경우의 수들)이 구해지게 된다. 

i-1일 경우에 1장짜리를 이미 산 경우이다. 그러면 N = 4 일 때의 경우의 수 중에 최대에서 뽑은 뒤 arr[1]을 더해준다. 

 

i-2일 경우에 2장짜리를 이미 산 경우이다. N = 3일 때의 경우의 수 중 최대에서 뽑은 뒤 arr[2]를 더해준다.

 

---

 

코드

package Dynamic_Programming;
 
import java.util.*;
import java.io.*;
 
public class Main {
    static int atoi(String str){
        return Integer.parseInt(str);
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int size = atoi(br.readLine());
 
        int arr[] = new int[size+1];
        int dp[] = new int[size+1];
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        for(int i = 1; i <= size; i++){
            arr[i] = atoi(st.nextToken());
        }
        
        /////////////////////////////////////////입력 끝
 
        for(int i = 1; i <= size; i++){
            for(int j = 0; j < i; j++){
                dp[i] = Math.max(dp[i], dp[j] + arr[i-j]);
            }
        }
 
        System.out.println(dp[size]);
    }
}