https://www.acmicpc.net/problem/15486
15486번: 퇴사 2
첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)
www.acmicpc.net
기존에 있던 퇴사 문제의 상위 난이도 버전 문제이다.
퇴사 문제를 인상깊게? 풀어서 푼지 거의 2년이 다 되어가는데도 풀이가 기억나는 상태라, 한 번 그대로 하고 제출해봤다.
테스트 케이스 통과 자체는 별 문제 없었지만, N이 150만인걸 보고 시간초과가 나겠다는 생각이 들었고, 역시나였다.
그래서 기존에 푼 방식을 버리고, 좀 방식을 바꿔서 짰다. 예전에 푼 코드도 올려둔다. 참고로 당시엔 C로 코딩했다
더보기
#pragma warning(disable:4996)
#include<stdio.h>
#include<stdlib.h>
typedef struct Plan {
int sum;
int time;
int pay;
}Plan;
int bigger(int x, int y) {
if (x > y) return x;
else return y;
}
int main() {
int n, i, j, max, index;
Plan *counsel;
scanf("%d", &n);
counsel = (Plan *)malloc(sizeof(Plan) * n);
for (i = 0; i < n; i++) {
scanf("%d %d", &counsel[i].time, &counsel[i].pay);
if ((i + counsel[i].time) > n) {
counsel[i].pay = 0; //N+1일 이후까지 상담이 진행되는 경우(할 수 없는 상담)
}
counsel[i].sum = counsel[i].pay;
}
for (i = 0; i < n; i++) {
if (counsel[i].time + i > n) {
continue;
}
else {
index = i + counsel[i].time;
for (j = index; j < n; j++) {
counsel[j].sum = bigger(counsel[j].pay + counsel[i].sum, counsel[j].sum);
}
}
}
max = 0;
for (i = 0; i < n; i++) {
if (max < counsel[i].sum) max = counsel[i].sum;
}
printf("%d", max);
}
기존의 방식은 특정 날에 상담을 진행하면, 그 상담에 소요되는 일만큼 지나고 그 뒤에 생기는 상담에 모두 pay를 추가하여 비교하는 식으로 했고,
아마 이번 문제에서는 해당 부분때문에 시간초과가 났을것으로 생각된다.(최대 O(N^2) 시간이 소요될 수 있기 때문)
import java.io.*;
import java.util.*;
public class boj15486 {
static int N, max;
static Meeting plans[];
public static void getMaxPay() {
int i, j;
for (i = 1; i <= N + 1; i++) {
max = Math.max(max, plans[i].sum);
j = i + plans[i].time;
if (j <= N + 1) {
plans[j].sum = Math.max(plans[j].sum, max + plans[i].pay);
}
}
max = Math.max(max, plans[N + 1].sum);
}
public static void pre() throws IOException {
int i;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
plans = new Meeting[N + 2];
max = 0;
for (i = 1; i <= N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
plans[i] = new Meeting(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
plans[i] = new Meeting(0, 0);
}
public static void main(String args[]) throws IOException {
pre();
getMaxPay();
System.out.println(max);
}
static class Meeting {
int pay, time, sum;
public Meeting() {
}
public Meeting(int time, int pay) {
this.pay = pay;
this.time = time;
this.sum = 0;
}
}
}
해당 문제에선 dp 배열을 따로 두는 대신 class 선언 후 객체의 sum이 dp배열에 담길 정보(최대 받을 수 있는 값)을 하게 했다.
plans[i]가 의미하는 것은 i일차 이전까지 누적해서 받을 수 있는 최대값으로, 그렇기 때문에 초기값은 0으로 해두고
맨 처음 탐색시 plans[1].sum == 0 이 되는 것이다.(1일차 이전에 누적해서 벌은 돈 = 0원)
N일차까지 일한 일당은 다음날에 반영되기 때문에, plans 배열의 크기는 N+2로 했고,
마지막에 반영되는 값이 최대값인지 확인해주기 위해 기존에 갱신되어왔던 max 값과 plans[N+1].sum 값을 비교하여 출력한다.
앞에 두 실행초과는 기존에 풀었던 방식을 그대로 해봤을때 남은 흔적이다.