[Problem Solving] BJ_14501. 퇴사

do_it·2025년 9월 28일

Problem Solving

problem-solving

목록 보기

2/14

1. 문제 설명

백준이가 N+1일째 되는 날 퇴사하기 위해

남은 N일 동안 최대한 많은 상담을 함
각 날짜마다 상담에 소요되는 일 수와 받을 수 있는 금액이 다름

이 때, 백준이가 얻을 수 있는 최대 수익?

Ti: i번째 날 상담을 했을 때 걸리는 일수
Pi: i번째 날 상담을 했을 때 받을 수 있는 금액

// [input]
7 // N (N+1일까지 상담 가능)
3 10 // 1일: 3일 소요 & 10의 이익
5 20 
1 10
1 20
2 15
4 40
2 200

2. 스크래치

0) 문제 유형 파악

수영장 문제와 유사 → dp 문제인데 점화식이 안 떠오름
각 날마다 상담을 선택할지 말지 결정, 상담 일정이 겹치면 불가능

1) 첫 번째 풀이: 백트래킹

각 날 마다 두 가지 선택지가 있음
1 - 상담을 한다 → Ti[i]일동안 상담 후 Pi[i]를 받음
2- 상담을 안 한다 → 다음 날로 넘어감

dfs(currentDay, currentDay)
	// base-case
    if currentDay > N: return sumTilNow
    
    1) 상담 선택:
    if currentDay + Ti[currentDay] <= N+1:
     dfs(currentDay + Ti[currentDay], sumTilNow + Pi[currentDay])
     
    2) 상담 미선택:
    dfs(currentDay + 1, sumTilNow)

백트래킹 문제점
문제에서 주어진 N의 범위 (1 ≤ N ≤ 15)에서는 가능하지만 중복 계산이 많음
N의 범위가 커지면 비효율적

2) 두 번째 풀이: DP (Bottom-up)

dp[i] 점화식 세우기
dp[i] = i번째 날 ~ 퇴사일까지 벌 수 있는 최대 수익
각 날의 선택 중의 최댓값
1 - 상담을 한다 → Pi[i] + dp[i+Ti[i]]
2- 상담을 안 한다 or 불가능→ 다음 날로 넘어감 dp[i+1]
⇒ 점화식: dp[i] = max(dp[i+1], Pi[i] + dp[i+Ti[i]])
dp 테이블을 어떻게 채우는가?
dp[i]를 구하기 위해서 점화식에서 dp[i+1]을 필요로 함
→ dp[i+1]이 이미 계산되어 있어야 함
⇒ dp 테이블을 뒤에서부터 채워야 함

3. 풀이

주요 알고리즘: DP (Bottom-up)

반복문 & dp 테이블 이용

// 1. dp 테이블 정의
// 문제에서 N이 주어짐 
// But 근무 가능한 날짜: 1일 ~ N+1일 => 1 ~ N+1 인덱스 필요
int[] dp = new int[N+2]; 

// 2. 점화식 채우기 (거꾸로)
for(int i=N; i>=1; i--) {
			// 상담 가능
			if(i+Ti[i]<=N+1) {
				dp[i] = Math.max(Pi[i]+dp[i+Ti[i]],dp[i+1]);
			}
			// 상담 불가능
			else {
				dp[i] = dp[i+1];
			}
}
// 3. 결과 반환

4. 코드


public class bj14501_퇴사_DP_BottomUp {
	static int Max = 0;
	static int N; // 앞으로 근무가 가능한 일 수
	static int[] Ti; // i번째날 상담을 했을 때 걸리는 일 수
	static int[] Pi; //i번째날 상담을 했을 때 받을 수 있는 금액
	static int[] dp;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// [input]
		N = Integer.parseInt(br.readLine());
		Ti = new int[N+1]; // 상담 완료 시간을 저장하는 배열, 1부터 시작
		Pi = new int[N+1]; // 받을 수 있는 금액 저장하는 배열
		dp = new int[N+2]; // 1일 ~ N+1일까지 상담 가능

	
		for(int i=1; i<=N; i++) {
			String[] temp = br.readLine().split(" ");
			Ti[i] = Integer.parseInt(temp[0]);
			Pi[i] = Integer.parseInt(temp[1]);
		}

		// [logic]
		// 점화식 채우기
		// dp[i]:i일부터 퇴사일까지 벌 수 있는 최대 수익
		for(int i=N; i>=1; i--) {
			// 상담 가능
			if(i+Ti[i]<=N+1) {
				dp[i] = Math.max(Pi[i]+dp[i+Ti[i]],dp[i+1]);
			}
			// 상담 불가능
			else {
				dp[i] = dp[i+1];
			}
		}
		Max = dp[1];
		
		// [output]
		System.out.println(Max);

	}// main

}

5. De-fault

[1] 점화식의 의미를 정확히 세우기

dp[i]가 무엇을 의미하는가?

dp[i] = i번째 ~ 퇴사일까지 벌 수 있는 최대 수익
i일에 상담을 선택할지 안 할지를 포함해서, i일부터 마지막 날까지 벌 수 있는 최대 돈

[2] DP테이블이 왜 거꾸로 채워져야 하는가?

Bottom-up DP에서 뒤에서부터 채우는 이유?

점화식에서 dp[i]를 계산하려면 i 이후의 날(dp[i+1], dp[i+Ti[i]])의 값이 이미 계산되어 있어야 함
점화식이 미래 상태를 참조하는 경우 뒤에서부터 채우기!

[3] 최종 결과값은 무엇을 찾아야 하는가?

문제에서 요구하는 답: 퇴사 전까지의 최대 수익
dp[i]의 정의에 따라 dp[1]이 문제에서 찾고자 하는 답

6. 시간 복잡도

1) 백트래킹

[시간복잡도]

재귀 호출 구조:
- 각 날마다 두 가지 선택 → 상담함 / 상담 안 함
- 재귀 트리 높이 = N (총 N일)
- 모든 경우의 수 탐색 → 최대 2^N
따라서 시간복잡도 = O(2^N)

⇒ 작은 N(예: ≤ 15)에서는 가능, N이 커지면 폭발적 증가

2) DP (Bottom-up)