문제
문제점 해결
처음 풀이로 쉽게 통과하긴 했지만 다시 소스코드를 보니 쉽게 풀 수 있는 부분을 어렵게 꼬아버린 것 같아서 문제에 대해 다시 생각해보았다.
int[] dp = new int[N];
for (int i = 0; i < N; i++) {
int time = consulting[i][0];
int cost = consulting[i][1];
if(i + time <= N && dp[i]) dp[i] = cost;
for (int j = i + time; j < N; j++) {
if(j + time < N) {
if(dp[j] == 0) dp[j] = dp[i] + cost;
else dp[j] = Math.max(dp[j], dp[i] + cost);
}
}
}
위의 코드는 처음 설계한 코드다. 처음엔 상담일이 N + 1을 초과하지 않을 때에만 dp 배열에 값을 저장했다.
int[] dp = new int[N + 1];
for (int i = 0; i < N; i++) {
int time = consulting[i][0];
int cost = consulting[i][1];
for (int j = i + time; j <= N; j++) {
if(dp[j] < dp[i] + cost) {
dp[j] = dp[i] + cost;
}
}
}
다음은 수정 후의 코드다. 확실히 전보다 깔끔하다고 생각한다. 2번째 풀이 방법은 현재 기준일(i)로 부터 상담일(time) 후 얻을 수 있는 비용(cost)을 저장하는 방법이다. 1일에 잡혀있는 상담일(time)은 3일이 걸리고 이후 4일에 상담을 할지 5일에 상담을 할지, 언제 하는 것이 최대비용을 얻을 수 있는지 아직 모르기 때문에 i + time 후의 날짜(dp 배열)에 현재 기준일에 해당하는 비용을 더해준다. 이때 주의할 점은 현재 기준일에 해당하는 비용을 더하는 것 보다 해당 날짜에 이미 저장된 비용이 더 크면 더해주지 않는다. 예를들어, 2일에 상담을 한 후 4일에 상담을 하는 비용보다 1일에 상담을 한 후 4일에 상담을 해서 더 큰 금액을 얻을 수 있다면 그 비용(1일 후 4일)을 유지해줘야 한다는 것이다.
이렇게 값을 갱신하다 보면 마지막 날(N)에 가장 큰 비용이 저장되고, 그 값을 출력해주면 된다.
풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] consulting = new int[N][2];
StringTokenizer st;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), " ");
consulting[i][0] = Integer.parseInt(st.nextToken());
consulting[i][1] = Integer.parseInt(st.nextToken());
}
int[] dp = new int[N + 1];
for (int i = 0; i < N; i++) {
int time = consulting[i][0];
int cost = consulting[i][1];
for (int j = i + time; j <= N; j++) {
if(dp[j] < dp[i] + cost) {
dp[j] = dp[i] + cost;
}
}
}
System.out.println(dp[N]);
}
}