백준 [자바 java] 11052번 : 카드 구매하기

이 문제는 카드 팩 별로 가격이 매겨진 카드들을 개수에 맞게 딱 사는 경우 중 가장 높은 가격을 구하는 문제이다. 처음에는 가성비가 가장 낮은 카드를 맞춰서 사는 방법을 생각했지만 너무 예외가 많았다. 그래서 dp에 1부터 차례로 값을 넣기로 했다. 예를 들어 dp [2]의 경우는 (2), (1,1)의 경우 중 더 비싼 것, dp [5]의 경우는 (1,4), (2,3), (5) 중 가장 비싼 것을 넣게 하였다. 이렇게 하면 세 묶음을 사는 경우를 굳이 고려하지 않아도 되기 때문이다. 

import java.io.*;
import java.util.*;



class Main {
	
	
	public static void main(String[] arg) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader (System.in));
		StringTokenizer st;
		
		
		int n = Integer.parseInt(br.readLine());
		st = new StringTokenizer(br.readLine());
		
		int i;
		int[] arr = new int[n+1];
		int[] dp = new int[n+1];
		
		for(i = 1;i<=n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		dp[1] = arr[1];
		int j;
		int nmax = 0;
		int kk;
		
		
		for(i = 2;i<=n;i++) {
			nmax = arr[i];
			for(j = 1;j<=i/2;j++) {
				kk = dp[j] + dp[i-j];
				nmax = Math.max(nmax,kk);
			}
			dp[i] = nmax;
		}
		System.out.println(dp[n]);
}

}

 실수는 딱히 안했다.

기억해야 할 점: 상식적으로 맞다고 생각하는 방법도 어쩔 때는 틀릴 때도 있다.(정석적인(?) 방법이 정답일 수도!)

다른 사람 코드와 다른 점 : dp배열을 딱히 안 만들고 바로 하는 방법도 있다. 

 

이번 문제는 dp 아닌 줄 알고 풀었는데 dp였다. 사람들이 어렵다는 dp문제를 어느 정도 터득해서 좋긴 하지만, 앞으로는 문제 풀기 전에 어떤 알고리즘인지 알게 되더라도 그냥 유형별로 골라서 풀어야 할지 고민해봐야겠다.