백준 1106 호텔

골드 5 입성 ㅎㅎ 바로어려워졌다..

https://www.acmicpc.net/problem/1106

바로메인로직 ㄱㄱ

잘보면 결국 출력이 돈의 최솟값이다

그렇다는것은

배열A[인원수] =돈
을 구하면된다..

그러면 인원수의 한계값을 알아야한다. 인원수는 무한대?..

헉.. 하지만 첫라인에 인원수의 값이 나온다 그리고 이값은 100보다 작거나 같은수이므로

결국 한계값은 C+100 으로 잡고 진행하면된다!

그리고 KNAPSACK 적용 // 입력을 받으면서 적용 OR 받고 한번에 돌리기

☆ knapsack을 0부터 시작하면 중복사용 o // 뒤에서부터타면 한번만적용

마지막으로 짱중요한거!! 배열은 0으로 초기화되고 최솟값이므로 max값 초기화를 해주고 냅색을 타는 조건을 원래에서는 0일때는 안타는 방향으로 햇지만 반대로 max 초기화기때문에 max값이면 변경을 안해주면! 냅색이 완성.

코드는 다음과같다.

public class 호텔 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		int c = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		
		int[] w = new int[n];
		int[] v = new int[n];
		
		int[] result = new int[c+101];
		for(int i=0;i<c+101;i++) {
			result[i] = Integer.MAX_VALUE;
		}

		
		for(int i=0;i<n;i++) {
			st= new StringTokenizer(br.readLine());
			w[i] = Integer.parseInt(st.nextToken()); //들인돈
			v[i] = Integer.parseInt(st.nextToken()); //사람인원수
			
			int count = (c+100)/v[i];
			for(int j=1;j<=count;j++) {
				int cur = v[i] * j; // 현재 인원수 
				if(result[cur]>w[i]*j) { 
					result[cur] = w[i]*j;
				}		}
			
		}
		//들인돈의 최소값을 구해야되고
		
		//홍보인원은 정해져있음

		
		
	
		
		//result[3명] = 최소금액 3원 이런식으로.. 
		
		for(int i=0;i<n;i++) {
			for(int j=v[i];j<c+101;j++) {
				if(result[j]>result[j-v[i]]+w[i] && result[j-v[i]] != Integer.MAX_VALUE) {
					result[j] = result[j-v[i]]+w[i];
				}
			}

		}
		
		int min = Integer.MAX_VALUE;
		for(int i=c;i<c+101;i++) {
			if(result[i]!=Integer.MAX_VALUE) {
				min = Math.min(min,result[i]);
			}
		}
		System.out.println(min);
	
	}
}