아이디어

• 고객 p[j]명을 늘리기 위해 co[j]의 비용이 든다고 하면...
  • 고객을 i명 늘이기 위한 최소 비용 memo[i]는 memo[i - p[j]] + co[j]의 최솟값이다.
• 고객을 '최소' C명 이상 늘리면 되므로 memo[C]~memo[C + (p[i]의 최댓값) - 1] 중 최솟값을 취해야 한다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer tk = null;

	static int C, N, maxp, ans;
	static int[] co, p;
	static int[] memo;	// 고객 i명을 늘이기 위한 최소비용
	
	static final int INF = Integer.MAX_VALUE / 2;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		C = Integer.parseInt(tk.nextToken());
		N = Integer.parseInt(tk.nextToken());
		
		
		co = new int[N];
		p = new int[N];
		for (int i=0; i<N; i++) {
			tk = new StringTokenizer(rd.readLine());
			co[i] = Integer.parseInt(tk.nextToken());
			p[i] = Integer.parseInt(tk.nextToken());
			maxp = Math.max(maxp, p[i]);
		}

		memo = new int[C + maxp];
		
		for (int i=1; i < C + maxp; i++) {
			memo[i] = INF;
			for (int j=0; j<N; j++) {
				if (i < p[j]) continue;
				memo[i] = Math.min(memo[i], memo[i - p[j]] + co[j]);
			}
		}
		
		ans = INF;
		for (int i = C; i < C + maxp; i++) {
			ans = Math.min(ans, memo[i]);
		}
		
		System.out.println(ans);
	}
}

메모리 및 시간

• 메모리: 14216 KB
• 시간: 128 ms

리뷰

• DP 재활 운동
• 배낭 문제로 풀 수 있나?