[Baekjoon] 14501_퇴사

문제(출처: https://www.acmicpc.net/problem/14501)

---

< 퇴사 >

 

문제 풀이 

 

dp를 활용하여 얻을 수 있는 최대 이익을 구한다. 

 

my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class _14501_ { // 퇴사
	static class Pair {
		int t, p;

		public Pair(int t, int p) {
			this.t = t;
			this.p = p;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		Pair arr[] = new Pair[n + 1];
		int dp[] = new int[n + 2];

		for (int i = 1; i < n + 1; i++) {
			st = new StringTokenizer(bf.readLine());
			arr[i] = new Pair(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}

		/* ex1)
		for (int i = 1; i < n + 1; i++) {
			if (i + arr[i].t < n + 2) {
				dp[i] = arr[i].p;
			}
		}

		
		for (int i = 2; i < n + 1; i++) {
			for (int j = 1; j < i; j++) {
				if (j + arr[j].t <= i && i + arr[i].t < n + 2)
					dp[i] = Math.max(dp[i], dp[j] + arr[i].p);
			}
		}
		*/

		for (int i = 1; i < n + 1; i++) {
			dp[i] = Math.max(dp[i], dp[i - 1]);
			if (i + arr[i].t < n + 2) {
				dp[i + arr[i].t] = Math.max(dp[i + arr[i].t], dp[i] + arr[i].p);
			}
		}

		int result = 0;
		for (int i = 1; i < n + 2; i++) {
			result = Math.max(result, dp[i]);
		}
		System.out.println(result);
	}

변수)
n : 일
arr : 상담 일정표
dp : 얻을 수 있는 이익
result : 얻을 수 있는 최대 이익 

 

일을 입력받는다. 일만큼 상담 일정을 입력받아 arr에 저장한다. 

 

처음에는 dp를 각 상담일에 얻을 수 있는 이익으로 초기화하고 이중 탐색을 통해 이전 날짜에서 현재 날짜에 상담할 수 있고, 현재 날짜에서 퇴사일까지 상담 가능한지 확인 후 dp를 업데이트하는 방법을 선택했다. 코드를 작성하고도 조금 헷갈려 다른 풀이를 찾아봤다.

 

하루씩 살펴보며 먼저 어제 값과 비교하여 최댓값으로 업데이트한다. 그다음 오늘 상담이 가능하다면 상담이 끝나는 날의 값을 업데이트한다. 최종 dp를 살펴보며 최댓값을 출력한다. 

---

---