b14501. 퇴사

 

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

 

 

 

✨ 자바로 푸는 퇴사 문제 풀이

 

---

 

📌 문제 개요

 

백준 14501번 “퇴사” 문제는 퇴사를 앞둔 상담원이 남은 N일 동안 최대한 많은 수익을 올릴 수 있도록 상담 일정을 최적으로 조정하는 DP(동적 계획법) 문제입니다.

 

각 날짜별로 상담을 진행할 경우 소요되는 일수와 받을 수 있는 보상이 주어지며, 퇴사 전까지 끝나는 상담만 수행할 수 있습니다.

 

---

 

💡 예제 입력

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

 

예제 출력

45

 

---

 

🛠 알고리즘 접근 방식

 

• dp[i]는 i일에 얻을 수 있는 최대 수익을 의미합니다.
• 각 날짜 i에서 상담을 할 수 있다면, i + days[i]일에 dp[i] + pays[i]를 반영합니다.
• 매일 상담을 하지 않아도 되므로 dp[i + 1]은 dp[i] 이상이 되어야 합니다.

 

---

 

✅ 핵심 아이디어

 

1. dp[i]: i일까지 얻을 수 있는 최대 수익
2. 상담 가능 여부: i + days[i] <= N일 때만 유효
3. 점화식:
   • dp[i + days[i]] = max(dp[i + days[i]], dp[i] + pays[i])
   • dp[i + 1] = max(dp[i + 1], dp[i])
4.  

 

---

 

🧾 코드 해설

 

 

🔍 입력 처리

int N = Integer.parseInt(br.readLine());
int[] days = new int[N];
int[] pays = new int[N];
int[] dp = new int[N+1];
for (int i = 0; i < N; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    days[i] = Integer.parseInt(st.nextToken());
    pays[i] = Integer.parseInt(st.nextToken());
}

 

📆 DP 로직

for(int i = 0; i < N; i++) {
    if(i + days[i] <= N){
        dp[i + days[i]] = Math.max(dp[i + days[i]], dp[i] + pays[i]);
    }
    dp[i + 1] = Math.max(dp[i + 1], dp[i]);
}

 

• 오늘 상담을 하면 i + days[i]일에 수익 반영
• 상담을 안 한다면 그냥 i + 1일로 넘김

 

 

✅ 결과 출력

System.out.println(dp[N]);

 

---

 

✅ 핵심 포인트 정리

 

• DP로 날짜별 최대 수익을 누적
• 상담 종료일이 퇴사일을 넘지 않도록 조건 체크
• dp[i + 1] = max(dp[i + 1], dp[i])을 통해 상담 미진행 시 보존 처리

 

---

 

🌌 결론: 선택의 연속에서 최선의 결정 만들기

 

단순한 누적이 아니라 ‘퇴사 전까지 가능한 상담 조합’ 중 최적의 선택을 찾아야 하는 문제입니다.

DP를 통해 점진적으로 최적해를 찾아가는 과정이 이 문제의 핵심