링크
https://www.acmicpc.net/problem/15486
문제 설명
정답률 39.258%
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
...
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
입력 예제
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200출력 예제
45풀이
이 문제는 상향식과 하향식 두가지 방식으로 풀 수 있다. 우선 상향식은 dp배열을 다음과 같이 정의한다.
dp[i]: 1일부터 i번째 날까지의 최대 수익N이 7로 주어질 때 1부터 7까지 생각해보면
- 1일은 3일의 시간이 걸리며 상담이 완료되면 4일이 된다.
- 이때 얻은 수익(10)과 기존 수익의 합을 4일까지의 수익(0)을 비교하여
dp[4]에 저장한다.
-dp = [0, 0, 0, 0, 10, 0, 0, 0, 0] - 2일은 5일의 시간이 걸리며 상담이 완료되면 7일이 된다.
- 이때 얻은 수익(20)과 기존 수익의 합을 7일까지의 수익(0)을 비교하여
dp[7]에 저장한다.
-dp = [0, 0, 0, 0, 10, 0, 0, 20, 0] - 3일은 1일의 시간이 걸리며 상담이 완료되면 4일이 된다.
- 이때 얻은 금액(10)과 기존 수익의 합을 4일까지의 수익(10)을 비교하여
dp[4]에 저장한다.
-dp = [0, 0, 0, 0, 10, 0, 0, 20, 0] - 4일은 1일의 시간이 걸리며 상담이 완료되면 5일이 된다.
- 이때 얻은 금액(20)과 기존 수익(10)의 합(30)을 5일까지의 수익(0)을 비교하여
dp[5]에 저장한다.
-dp = [0, 0, 0, 0, 10, 30, 0, 20, 0] - 5일은 2일의 시간이 걸리며 상담이 완료되면 7일이 된다.
- 이때 얻은 금액(15)과 기존 수익(30)의 합(45)을 7일까지의 수익(20)을 비교하여
dp[7]에 저장한다. - 수익은 누적돼야 하므로
dp[6]에dp[5]를 저장한다.
-dp = [0, 0, 0, 0, 10, 30, 30, 45, 0] - 6일은 4일의 시간이 걸리며 퇴사일이 지나므로 상담을 진행할 수 없다.
-dp = [0, 0, 0, 0, 10, 30, 30, 45, 0] - 7일은 2일의 시간이 걸리며 퇴사일이 지나므로 상담을 진행할 수 없다.
- 수익은 누적돼야 하므로
dp[8]에dp[7]를 저장한다.
-dp = [0, 0, 0, 0, 10, 30, 30, 45, 45]
Bottom-Up 방식으로 구현하면 다음과 같다. 만약 4일의 경우 1일 동안 상담을 진행하면 의미상 상담 종료일은 당일인 4일이 되지만 여기서는 5일로 생각한다.
for (int i = 1; i <= N; i++) {
//다음 날로 현재까지의 최대 수익 전달
dp[i + 1] = max(dp[i + 1], dp[i]);
int end = i + times[i]; //상담 종료일
if (end <= N + 1) { //퇴사일 전에 상담 가능
//상담 종료일까지의 최대 수익과 현재 일자에 상담을 진행할 경우와 비교
dp[end] = max(dp[end], dp[i] + profits[i]);
}
}
System.out.println(dp[N + 1]);하향식에선 dp배열을 다음과 같이 정의한다.
dp[i]: i번째 날 이후로의 최대 수익바로 코드로 넘어가면 하향식은 미래의 값으로 현재의 값을 구하는 것으로 상담이 가능할 경우 상담 종료일 후로의 최대 수익과 현재 일자의 수익의 합을 상담을 하지 않았을 때의 수익과 비교하여 갱신해나간다.
for (int i = N; i > 0; i--) {
int end = i + times[i]; //상담 종료일
if (end <= N + 1) { //퇴사일을 넘지 않은 경우 상담 가능
//i번째 날 상담을 할 경우와 안 할 경우 비교
dp[i] = max(dp[end] + profits[i], dp[i + 1]);
} else { //상담 불가
dp[i] = dp[i + 1];
}
}
//1번째 날부터 상담 시작시 최대 수익
System.out.println(dp[1]);전체 코드
//백준
public class Main {
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] dp = new int[N + 2]; //i번째 날 상담 시작 시 최대 수익
int[] dp2 = new int[N + 2]; //i번째 날까지 최대 수익
int[] times = new int[N + 1];
int[] profits = new int[N + 1];
for (int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
times[i] = Integer.parseInt(st.nextToken());
profits[i] = Integer.parseInt(st.nextToken());
}
//for (int i = N; i > 0; i--) {
// int end = i + times[i]; //상담 종료일
// if (end <= N + 1) { //퇴사일을 넘지 않은 경우 상담 가능
// //i번째 날 상담을 할 경우와 안 할 경우 비교
// dp[i] = max(dp[end] + profits[i], dp[i + 1]);
// } else { //상담 불가
// dp[i] = dp[i + 1];
// }
//}
//
////1번째 날부터 상담 시작시 최대 수익
//System.out.println(dp[1]);
for (int i = 1; i <= N; i++) {
//다음 날로 현재까지의 최대 수익 전달
dp2[i + 1] = max(dp2[i + 1], dp2[i]);
int end = i + times[i]; //상담 종료일
if (end <= N + 1) { //퇴사일 전에 상담 가능
//상담 종료일까지의 최대 수익과 현재 일자에 상담을 진행할 경우 비교
dp2[end] = max(dp2[end], dp2[i] + profits[i]);
}
}
System.out.println(dp2[N + 1]);
}
}
백엔드