[백준, 15486, G5] 퇴사 2

0. 문제 링크

https://www.acmicpc.net/problem/15486

15486번: 퇴사 2

---

1. 문제 핵심

1. 퇴사일인 N+1일 전까지인 N일 동안 최대한 최대 수익이 가능한 상담일정을 잡는 것
2. 한 상담을 맡게 되면 그 상담이 끝날 때까지 다른 상담은 받지 못함.

---

2. 문제 접근

1. DP문제이기 때문에 dp배열을 하나 만들어주었고 dp 배열은 그 날 최대로 벌 수 있는 비용을 저장합니다.
2. 각 일자별에 종료되는 상담 일정을 저장하기 위해 Stack배열을 만들어두었습니다. 그리고 각 요일마다 있는 상담의 종료일에 해당 상담의 시작일과 비용을 Stack에 저장했습니다. (메모리 크기를 줄이고자 Stack을 배열로 변경하려 했으나 N이 최대 150만개이기 때문에 오히려 메모리 초과가 났습니다.)
3. 이제 1일부터 N일까지 각 요일을 순회하며 해당 일자에 종료되는 상담 수익 + 해당 상담이 시작되기 가장 직전의 누적 최고 상담 수익을 계산해주고 그것과 그 전날 최고 상담 누적 수익과 비교해 더 큰 수익을 저장해줍니다.
4. 만약 특정 일자에 상담이 없다면 해당 일자는 이전의 최고 누적 상담 수익을 저장해줍니다.
5. 이렇게 마지막 요일까지 진행하면 마지막 요일에는 최고 수익이 저장되게 됩니다.

 

velog로부터 생성

---

3. 코드 분석

각 일자에 종료되는 상담을 저장해줄 Stack 선언

처리 불가능 상담은 저장 X, 상담일의 종료일에 해당 상담의 시작일과 수익을 저장

각 일자별 저장된 상담을 확인하며 최대 수익을 계산. 마지막으로 전날 수익과 비교해 최대 수익을 갱신

---

4. 베스트 코드 분석

---

5. 코드

import java.io.*;
import java.util.*;

public class Main {
	static class Reader {
		final private int BUFFER_SIZE = 1 << 18;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[BUFFER_SIZE]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n') {
					if (cnt != 0) {
						break;
					} else {
						continue;
					}
				}
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

	public static void main(String[] args) throws IOException {
		Reader br = new Reader();
		int N = br.nextInt();
		int[] dp = new int[N + 1];
		Stack<int[]>[] pq = new Stack[N + 1];
		for (int i = 1; i <= N; i++) {
			pq[i] = new Stack<>();
		}
		int e, v;
		for (int i = 1; i <= N; i++) {
			e = br.nextInt();
			v = br.nextInt();

			// N일 내에 처리할 수 없는 상담
			if (i + e - 1 > N)
				continue;
			// 시작일, 종료일, 수익
			pq[i + e - 1].add(new int[] { e, v });
		}
		int[] crnt;
		for (int i = 1; i <= N; i++) {
			while (!pq[i].isEmpty()) {
				crnt = pq[i].pop();
				dp[i] = Math.max(dp[i], dp[i - crnt[0]] + crnt[1]);
			}
			dp[i] = Math.max(dp[i], dp[i - 1]);
		}
		System.out.println(dp[N]);
	}
}