1106_호텔 **** (감도 안 왔음)

사용 알고리즘: dp

사용 언어: java

 

package week04;

import java.util.Arrays;
import java.util.Scanner;

public class Main_bj_1106_호텔 {
	
	static int c, n, costs[][];
	static int[] dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		c = sc.nextInt(); //적아도 C명에게 홍보
		n = sc.nextInt(); //홍보 가능 도시 개수
		
//		costs = new int[n][2]; //비용, 비용 당 유치 가능 고객
		
//		for(int i=0; i<n; i++) {
//			int a = sc.nextInt();
//			int b = sc.nextInt();
//			costs[i][0] = a;
//			costs[i][1] = b;
//		}
		//입력 완료
		
		dp = new int[c+100]; //문제: 비용으로 얻을 수 있는 고객의 수<=100
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		
		for(int i=0; i<n; i++) {
			int cost = sc.nextInt();
			int people = sc.nextInt();
//			costs[i][0] = cost;
//			costs[i][1] = people;
			
			for(int j=people; j<c+100; j++) {
				//돈의 정수배 만큼 투자
				
				/**
				 * j는 항상 입력받은 people부터 시작하니까,
				 * 맨 처음 dp[j - people]은 곧 dp[people - people]이 되어
				 * dp[0]을 나타냄.
				 * => dp[0]은 0으로 초기화 했으므로, Integer.MAX_VALUE가 아님
				 * dp[j] = Math.min(dp[j], cost + dp[j - people]);를 항상 수행
				 * 
				 * j가 1씩 더해짐에 따라,
				 * dp[j - people]의 값은 Integer.MAX_VALUE가 됨
				 * 
				 * 그러다가 j = 돈의 정수배 가 되면,
				 * dp[10(j) - 5(people)] = dp[5]가 되므로,
				 * 돈의 정수배 자리에서는 dp[j - people] != Integer.MAX_VALUE임.
				 * 따라서 dp[j] = Math.min(dp[j], cost + dp[j - people]);수행
				 * 
				 * 이런 식으로 현재 입력 받은 돈의 정수배 인덱스에 해당하는 dp값만
				 * 최소값으로 갱신.
				 */
				
				if(dp[j - people] != Integer.MAX_VALUE) {
					dp[j] = Math.min(dp[j], cost + dp[j - people]);
				}
			}
		}//
		
		int ans = Integer.MAX_VALUE;
		for (int i = c; i < c+100; i++) {
			ans = Math.min(ans, dp[i]);
		}
		System.out.println(ans);
		
	}

}

 

도대체... 다시 풀어보기