알고리즘/백준
1106_호텔 **** (감도 안 왔음)
베리영young
2024. 6. 22. 23:04
사용 알고리즘: 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);
}
}
도대체... 다시 풀어보기