https://www.acmicpc.net/problem/15486
#15486: 포기 2
첫 번째 줄은 N(1 ≤ N ≤ 1,500,000)을 지정합니다.
2번째 줄부터 N번째 줄까지는 Ti와 Pi를 공백으로 구분하여 1번째부터 N번째까지 순서대로 부여한다.
(1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)
www.acmicpc.net
문제
컨설턴트로 일하는 백준이 사직을 앞두고 있다.
N+1에서 오늘부터 회사로. 남은 N일 동안 최대한 많은 상담을 하려고 노력합니다.
백준이는 비서에게 최대한 많은 상담 일정을 잡아달라고 부탁했고 비서는 어느 날 여러 사람과 상담 일정을 잡았다.
각 상담은 상담을 완료하는 데 걸리는 시간에 대한 $T_i$와 상담 완료 후 얻을 수 있는 $P_i$의 금액으로 구성됩니다.
N=7인 경우 다음과 같은 상담 계획을 고려한다.
1일 2일 3일 4일 5일 6일 7일 티피
| 1 일 | 2일 | 3 일 | 4 일 | 5 일 | 6 일 | 7 일 | |
| $T_i$ | 삼 | 5 | 하나 | 하나 | 2 | 4 | 2 |
| $P_i$ | 10 | 20 | 10 | 20 | 15 | 40 | 200 |
1일 예정된 상담은 총 3일간 진행되며 상담 시 받을 수 있는 금액은 10개입니다.
5일 예정된 상담은 총 2일 진행되며 15개를 받을 수 있습니다.
상담 기간이 하루 이상 길어질 수 있기 때문에 모든 상담이 진행되지는 않습니다.
예를 들어 1일에 상담을 했다면 2일과 3일에는 상담을 할 수 없습니다.
2일 상담이 있을 경우 3, 4, 5, 6일 예정된 상담에 참석하실 수 없습니다.
내가 N + 1에 있기 때문에. 그 날 회사에 없으면 6일이나 7일에도 상담을 할 수 없습니다.
퇴사 전 상담의 최대 편익은 1일차, 4일차, 5일차 상담이며, 이때의 효용은 10 + 20 + 15 = 45입니다.
상담이 제대로 이루어졌을 때 백준이 얻을 수 있는 최대 이익을 찾는 프로그램을 작성하시오.
기입
첫 번째 줄은 N(1 ≤ N ≤ 1,500,000)을 지정합니다.
$T_i$ 및 $P_i$는 두 번째 줄부터 N줄로 지정되며 공백으로 구분되고 1번째부터 N번째까지 순서대로 지정됩니다.
(1 ≤ $T_i$ ≤ 50, 1 ≤ $P_i$ ≤ 1,000)
누르다
첫 번째 줄에는 백준이 얻을 수 있는 최대 승리를 입력합니다.
예시 입력 1
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200예제 출력 1
45
샘플 입력 2
10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10샘플 출력 2
55
샘플 입력 3
10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6샘플 출력 3
20
샘플 입력 4
10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50예제 출력 4
90import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String() args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
// N 입력
int N = Integer.parseInt(br.readLine());
int() profit = new int(N + 2); // 인덱스일 별 최대 수익
int maxProfit = 0; // 현재 일수에서 벌어 놓은 있는 최대 이익
int result = 0; // 가장 큰 이익
for (int i = 1; i < N + 1; i++) { // 1일부터 N일까지
// i일에 시작할 수 있는 일 정보를 입력 받고
st = new StringTokenizer(br.readLine());
int day = Integer.parseInt(st.nextToken());
int pay = Integer.parseInt(st.nextToken());
maxProfit = Math.max(maxProfit, profit(i - 1)); // 전날까지 벌어놓은 최대 이익을 구한다
// i일에 일을 시작해서 i + day - 1에 일이 끝났을 때의 최대 이익을 profit에 저장한다
if(i + day - 1 <= N) {
profit(i + day - 1) = Math.max(profit(i + day - 1), maxProfit + pay);
result = Math.max(result, profit(i + day - 1));
}
}
System.out.println(result);
}
}