문제
보자마자 DP 문제라는 것을 알았다. 그리고 DP중에서도 냅색 문제라고 생각했다. 그런데 일반적인 냅색 문제와는 달랐다.
일반적인 냅색 문제는
0-1냅색문제로 짐이 1번 들어가거나 0번들어가거나 둘 중 하나의 경우인 상황이다.
그러나 이 문제를 보면 짐(여기서는 도시)이 1번이 아닌 여러번 들어갈 수 있다.
따라서 이 문제는0-1냅색 문제를 응용해야한다는 것을 느꼈다.
풀이 방법
1. DP 배열을 어떻게 만들지 구상하기
먼저 DP 배열을 어떻게 만들지 구상해야한다. 기존의 냅색 문제는 DP 배열을 두가지로 만들 수 있다.
1차원 배열
- dp[i]
- 행: 최대 허용 가능한 무게
- dp[i]: 는 무게가 최대 i까지 허용될 때 모든 짐을 고려하여 얻을 수 있는 최대 효용
2차원 배열
- dp[i][j]
- 열: 각 짐들의 개수(각 짐)
- 행: 최대 허용 가능한 무게
- dp[i][j]: 는 무게가 최대 j까지 허용될 때 짐 i개(예를 들어 1번짐부터 i번짐)를 고려했을 때 얻을 수 있는 최대 효용
그렇다면 현재 문제에서는 dp배열을 어떻게 만들어야할까?
이번 문제에서는 1차원 배열을 만들고 각 행은 최대 허용 가능한 무게를, dp[i]의 값은 i가 최대 허용 가능 무게일 때 최소 비용이다.
이 문제에서 주어진 조건을 바꿔서 말하면 다음과 같다.
1차원 배열
- dp[i]
- 행 고객 수
- dp[i] 고객수가 i명을 유치하기 위한 최소 비용
배열의 길이는 몇으로 해야할까?
언뜻보면 C라고 생각할 수 있다. 하지만 결과적으로 C+100으로 해주어야한다. 배열에서 각 인덱스의 의미는 고객 수이다. i가 100이면 100명의 고객을 유치할 때의 최소 비용이 dp[i]이고, i가 101이면 101명의 고객을 유치할 때의 최소 비용이 dp[i]이다.
예를 들어 A도시는 3명을 유치하는 데에 5의 비용이 들고, B도시는 1명을 유치하는 데에 10의 비용이 든다고 가정해보자.
dp[1] = 10 이고 dp[2] = 20 인데 dp[3] = 5이다.
정확히 i명을 유치하는 데에 필요한 비용이므로 C명을 유치하는 데에 필요한 비용은 dp[C]이지만 최소 C명을 유치하는 비용은 dp[C+a] 일 수 있다.
그럼 여기서 a는 어떻게 정할까?
최대 사람 수가 100이므로 C+100을 해주면 더이상 유치할 수 없는 경우까지 안전하게 계산해준다.
2. DP 배열을 어떻게 채울지 구상하기
이제 DP배열을 만들었으니 어떻게 채울지를 결정해야한다.
기존의 0-1냅색 문제의 1차원 배열은 아래와 같은 식으로 채워주었다.
for(int i=1; i<=N; i++){
for(int w=Limit; w>=value[i]; w--){
dp[w] = Math.Max(dp[w], dp[w - weigth[i]]+ value[i]);
}
}이번에는 최소를 구해주어야하므로 Min을 사용해야한다. 그런데 0-1 냅색 문제에서는 따로 배열을 초기화하지 않았는데 그 이유는 배열을 선언하면 0으로 초기화 되기 때문이다. 그리고 Math.max()를 사용하므로 0으로 초기화해주는 것이 맞다.
하지만 이번에는 Math.min()을 사용해야하므로 배열들을 MAX_VALUE로 초기화해주어야한다. 또한 dp[0] = 0으로 초기화해준다. 이 의미는 0명을 유치하기 위한 비용은 0이라는 의미이다.
이제 초기화는 했으니 dp[1]부터 채워나가야한다.
dp[i]는 i명을 유치하기 위한 최소 비용이므로 dp[i]와 dp[i-현재 도시의 유치 가능한 사람 수]+ 현재 도시의 사람들을 유치하는 데에 드는 비용 중 최소값을 dp[i]로 설정해야한다.
그런데 이 때 주의할 점이 있다. 바로
dp[i-현재 도시의 유치 가능한 사람 수]가 우리가 초기화한MAX_VALUE가 아닌 경우에만 위 점화식을 사용해야한다는 것이다.
왜냐하면 우리가 초기화한MAX_VALUE는 해당 사람을 유치하는 방법이 없다는 것을 의미하기 때문이다. 따라서i-현재 도시의 유치 가능한 사람 수명을 유치하는 방법은 존재하지 않은 것이므로 계산할 수 없다.
따라서 코드는 아래와 같이 된다.
// DP 배열 채우기
for (int j = v; j < C + 100; j++) {
//만약 dp배열에서 현재 사람 수를 뺀 사람 명수의 비용이 초기 비용이 아니면 (초기 비용으로 초기화한 것은 만족시킬 수 없는 상태를 나타냄으로)
if(dp[j-v] != Long.MAX_VALUE){
//현재 배열 값과 현재 배열에서 v명을 빼고 i번째 사람을 넣었을 때의 비용 중 작은 것으로 결정
dp[j] = Math.min(dp[j], dp[j - v] + c);
}
}3. DP 배열을 통해 답을 어떻게 도출할지 생각하기
그렇다면 이렇게 DP배열을 만들었을 때 답은 어떻게 구할까?
아까 말했듯 dp[C]는 답이 될 수도 있고 아닐 수도 있다. 따라서 C ~ C+99까지의 dp[i] 중 가장 작은 것을 답으로 설정해야한다.
이번 문제는 DP의 응용이어서 상당히 오랜 시간이 걸렸지만, 실제 코테에서는 DP를 심화하여 내기가 어려움으로 너무 걱정하진 않아도 될 것 같다.
정답 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class p1106_2 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
// 입력 받기
st = new StringTokenizer(br.readLine());
int C = Integer.parseInt(st.nextToken()); // 목표 인원 수
int N = Integer.parseInt(st.nextToken()); // 도시 수
long[] dp = new long[C + 100]; //DP 배열 -> 최대 손님은 100명인데 103명을 하는게 더 최소일 수도 있고, 104명을 하는게 더 최소일 수도 있어서 C에 100을 더함
// dp[i] = i명의 사람을 유치하기 위한 최소 비용
Arrays.fill(dp, Long.MAX_VALUE); // 초기화를 최대값으로 함 -> 나중에 min을 할 것이기 때문에 음수 값으로 하면 안됨
// dp[0]을 0으로 초기화
dp[0] = 0; // 0명을 유치하기 위한 비용은 0임
// 비용과 인원 데이터 받기
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int c = Integer.parseInt(st.nextToken()); // 비용
int v = Integer.parseInt(st.nextToken()); // 모집 가능한 인원 수
// DP 배열 채우기
for (int j = v; j < C + 100; j++) {
if(dp[j-v] != Long.MAX_VALUE){ //만약 dp배열에서 현재 사람 수를 뺀 사람 명수의 비용이 초기 비용이 아니면 (초기 비용으로 초기화한 것은 만족시킬 수 없는 상태를 나타냄으로)
dp[j] = Math.min(dp[j], dp[j - v] + c); //현재 배열 값과 현재 배열에서 v명을 빼고 i번째 사람을 넣었을 때의 비용 중 작은 것으로 결정
}
}
}
// 답 찾기
long min = Long.MAX_VALUE;
for (int i = C; i < C + 100; i++) { //C명 이상을 유치하는 비용 중 가장 작은 비용을 값으로 설정
min = Math.min(dp[i], min);
}
// 출력
bw.write(min + "\n");
bw.flush();
bw.close();
}
}
