[백준]_1106_호텔

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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

public class B1106 {
	static int C,N;
	static int [] price,custom, arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		C = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		arr = new int[1001];
		price = new int[N];
		custom = new int[N];
		for(int i= 0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			price[i] = Integer.parseInt(st.nextToken());
			custom[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(cal(C,N));
	}

	static int cal(int c, int n) {
		int min=100000, temp=0;
		// c가 범위를 넘어설 경우(최소이기 때문에 값 이상을 넘어 갈 수도 있음)
		if(c<=0) return 0;
		// 값이 이미 존재
		else if(arr[c]>0)
			return arr[c];
		// 이전 값과 새로운 price를 더함.
		for(int i=0;i<n;i++) {
			temp = cal(c - custom[i],n) + price[i];
			min = temp < min ? temp : min;
		}
		// 최소 값 할당
		arr[c] = min;
		return min;
	}
}