
https://www.acmicpc.net/problem/1106
문제분석
DP의 핵심인 점화식을 찾는것이 너무 어려운 것 같다. 아직 DP문제에 익숙하지 않아서 인 것 같기도하고...
이 문제는 dp배열의 index를 인원, 저장하는 값을 최소 비용 으로 세팅한 뒤, 하나하나 해 나가는 것 이다. 저번에 풀었던 냅색 문제와 동일한 줄 알았는데, 한가지 다른 점 이 있다. 바로 같은 도시에 홍보를 2번, 3번.. 정수배로 할 수 있다는 것이다. 따라서, for문을 순회할 때 도시->인원 순으로 순회하면서 진행해야 해를 구할 수 있다.
코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[]args)throws IOException{
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[][] citys = new int[N+1][2]; // 도시 홍보 {비용, 고객 증가분}
citys[0][0]=0;
citys[0][1]=0;
for(int i = 1; i < N + 1; i++){
st = new StringTokenizer(br.readLine());
citys[i][0] = Integer.parseInt(st.nextToken());
citys[i][1] = Integer.parseInt(st.nextToken());
}
int[] dp = new int[C+101]; // index는 유치하는 인원, value는 최소 비용
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0]=0;
for(int j = 1; j < citys.length; j++){ // city 인덱스
int cost = citys[j][0];
int value = citys[j][1];
for(int i = value; i < dp.length; i++){ // dp 인덱스
if(dp[i-value]!=Integer.MAX_VALUE){ // 인원(i)보다, 해당 city 최소 증가분이 작은 경우만 계산 가능
dp[i] = Math.min(dp[i-value]+cost,dp[i]);
}
}
}
int result = Integer.MAX_VALUE;
for(int i = C; i < dp.length; i++){
result = Math.min(result,dp[i]);
}
System.out.println(result);
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 2618 경찰차 (0) | 2025.08.20 |
|---|---|
| [JAVA] 백준 3687 성냥개비 (2) | 2025.08.17 |
| [JAVA] 백준 12865 평범한 배낭(with knapsack) (3) | 2025.08.15 |
| [JAVA] 백준 1202 보석도둑 (3) | 2025.08.13 |
| [JAVA] 백준 16402 제국 (5) | 2025.08.06 |