https://www.acmicpc.net/problem/14501
문제
> 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
> 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
> 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고,
비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
> 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
> N = 7인 경우에 다음과 같은 상담 일정표를 보자.
1일 2일 3일 4일 5일 6일 7일
Ti 3 5 1 1 2 4 2
Pi 10 20 10 20 15 40 200
> 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다.
> 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
> 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
> 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다.
> 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
> 또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
> 퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며,
이때의 이익은 10+20+15=45이다.
> 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.접근
dp를 사용하여 해당 날짜에 각각 얼마나 벌 수 있나를 계산해 나간다.
각 날에 대해, 일을 할 떄와 안할 때로 나눠줘야한다.
먼저 오늘 일을 안하게 되면 내일 내가 번 돈은 어제 번돈+0, 오늘 번돈 중에 더 큰돈이 된다. 일을 안한 경우는 내가 다른 날 잡은 상담 때문에 해당 일에 일을 못할 경우를 말한다.
이제 일을 하면 내가 3일째 떄 2일짜리 일을 하면 5일 째 되는날 번 돈은 3일째까지 번돈 + 2일짜리일, 기존에 5일 째 벌어놨던 돈 중 더 큰 돈이 된다. 여기서 기존에 5일 돈은 다른 경우인 2일 째에서 3일짜리일을 헀다거나, 1일째에서 4일 짜리일은 한경우가 된다.
이렇게 모두 일자별 번 돈을 구하고 그 중 가장 돈을 많이 번 일자를 골라 출력한다.
문제해결
> 상담이 퇴사일인 N+1일에 끝나는 경우도 가능하므로 크기를 16으로 주는데 일을 안한 경우를 위해 +1일 해서 17일로 준다.
> Ti와 Pi를 입력받고 먼저 일을 안한 경우를 따져준다.
> 다음날의 번돈 dp(i+1)은 dp(i)와 dp(i+1)중 더 큰 돈이다.
> 이제 일 할 경우를 따지전 i+Ti가 N+1보다 커질때, 즉 상담이 퇴사날 이후 끝날 경우를 제해준다.
> 이제 해당 상담을 했을 때, 끝나는 날에 버는 돈은 현재날 + 해당 상담의 비용과 그날 끝나기로 예정됐던 다른 경우의 수들 중 더 큰 값이다.
> 모든 일자 중 가장 많은 돈을 버는 일자의 금액을 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//14501번 퇴사
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] dp = new int[17];
for(int i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int Ti = Integer.parseInt(st.nextToken());
int Pi = Integer.parseInt(st.nextToken());
dp[i+1] = Math.max(dp[i], dp[i+1]);
if(i + Ti > N+1) continue;
dp[i+Ti] = Math.max(dp[i] + Pi, dp[i+Ti]);
}
int rst = 0;
for(int i : dp) rst = Math.max(rst, i);
System.out.print(rst);
}
}
후기
일을 안하고 넘긴다 라는 개념을 빼먹어서 헤맸다.
