문제설명
입력 & 출력
나의 풀이
문제 접근 방법
"백준 - 퇴사" 문제는 퇴사 전 최대 수익을 창출할 수 있는 상담을 선택하여 최대 수익을 내는 것 입니다.
- 상담 기간과 수익이 주어지며, 특정 상담을 수행하면 해당 상담 기간만큼의 날이 소요됩니다.
- 퇴사일 이후로 상담이 넘어가면
해당 상담은 수행할 수 없습니다. - 최대 수익을 구하기 위해 DP를 활용합니다.
문제 자체는 어렵지 않으나 점화식을 도출하는 과정이 까다롭습니다. 우리의 목표는 퇴사 전 최대 수익을 뽑는 것인데, 각 날짜에서 상담을 선택하거나 선택하지 않는 경우를 고려하고, 이전까지의 최적해를 활용하여 현재의 최적해를 구하는 동적 계획법의 특성을 잘 활용해야 합니다.
특히 상담이 걸리는 기간과 수익을 고려하면서 dp 배열에 각 날짜까지의 최대 수익을 저장하고, 이를 활용하여 최종적으로 퇴사일까지의 최대 수익을 구할 수 있습니다.
말 보다 그림으로 보는 것이 편하기 때문에..
위와 같이 각 날짜에서 최대 수익을 저장하는 DP 배열을 사용하여 예제 1번의 정답을 도출하는 과정을 살펴보겠습니다.
그 전에 정리하자면:
- i : 현재 날짜
- T[i] : i일에 시작하는 상담이 걸리는 기간
- i + T[i] : i일에 시작한 상담이 끝나고 난 다음 날
- P[i] : i일에 시작하는 상담의 수익
- dp[i] : i일까지 얻을 수 있는 최대 수익
1 일차 : 오늘(i일) 상담을 했을 때 상담이 끝나는 날의 최대 수익은, 그 날짜에 이미 계산된 수익과 (오늘까지의 최대 수익 + 오늘 상담 수익) 중 더 큰 값을 선택합니다.
2 일차 : 마찬가지로 오늘(2일) 상담을 했을 때 상담이 끝나는 날(7)의 최대 수익은, 7일차의 이미 계산된 수익과 (2일차까지의 최대 수익 + 오늘 상담 수익 : 20) 중 더 큰 값을 선택합니다.
3 일차 : 마찬가지로 오늘(3일) 상담을 했을 때 상담이 끝나는 날(4)의 최대 수익은, 4일차의 이미 계산된 수익과 (3일차까지의 최대 수익 + 오늘 상담 수익 : 10) 중 더 큰 값을 선택합니다.
4 일차 : 오늘(4일) 상담을 했을 때 상담이 끝나는 날(5)의 최대 수익은, 5일차의 이미 계산된 수익과 (4일차까지의 최대 수익 + 오늘 상담 수익 : 20) 중 더 큰 값을 선택합니다.
5 일차 : 오늘(5일) 상담을 했을 때 상담이 끝나는 날(7일)의 최대 수익을 계산합니다.
7일차에는 이미 2일차 상담으로 인한 수익 20만원이 저장되어 있습니다. 이것과 (5일차까지의 최대 수익 30만원 + 5일차 상담 수익 15만원 = 45만원)을 비교합니다. 45만원이 기존 값인 20만원보다 크므로 dp[7]은 45만원으로 업데이트됩니다.
6일차 : 6일차에 상담을 시작하면 상담이 끝나는 날은 10일(6 + 4)입니다. 따라서 이 상담은 퇴사일(8일)을 초과하기 때문에 선택할 수 없습니다. dp[10] = max(30 + 40, 45)와 같은 계산은 의미가 없습니다
즉, 문제의 핵심은 퇴사 전까지 최대의 수익을 내야하는 것이기 때문에, 오늘 상담했을 때 퇴사일을 넘어가지 않는 선에서 최대한 효율적인 상담을 해야합니다.
따라서 1일차부터, 상담이 끝났을 때 다음날의 최대 수익을 저장하고, 각 날짜에서 이미 계산된 최대 수익과 새로운 상담을 했을 때의 수익을 비교하면서 최적의 해를 찾아갑니다.
왜냐하면 같은 날짜에 도달할 수 있는 여러 가지 경우가 존재하기 때문입니다. 예를 들어 7일차에는:
- 2일차에 시작한 상담(5일 소요)으로 20만원을 벌 수 있고
- 5일차에 시작한 상담(2일 소요)과 이전 수익을 합쳐 45만원을 벌 수 있습니다.
이처럼 같은 날짜에 도달하더라도 어떤 상담들을 선택했는지에 따라 수익이 달라질 수 있으므로, 매번 최대값을 비교하고 저장하면서 최적의 해를 찾아가는 것입니다.
전체 코드
상담이 불가능한 경우(퇴사일을 초과한다면) 현재값(dp[i+1])과 이전까지의 최대 수익(dp[i]) 중 더 큰 값을 선택하여 최소한 이전까지의 최대 수익은 보장받을 수 있도록 합니다.
'Coding Test > 백준' 카테고리의 다른 글
| [백준, 11279번] 최대 힙 (우선순위 큐, Java) (0) | 2025.01.07 |
|---|---|
| [백준, 2193번] 이친수 (다이나믹 프로그래밍 : DP, Java) (0) | 2025.01.06 |
| [백준, 1927] 최소 힙 (우선순위 큐, Java) (1) | 2025.01.03 |
| [백준, 10844번] 쉬운 계단 수 (다이나믹 프로그래밍 : DP, Java) (2) | 2025.01.03 |
| [백준, 2156번] 포도주 시식 (다이나믹 프로그래밍 : DP, 동적 계획법 , Java) (2) | 2025.01.01 |
문제설명
입력 & 출력
나의 풀이
문제 접근 방법
"백준 - 퇴사" 문제는 퇴사 전 최대 수익을 창출할 수 있는 상담을 선택하여 최대 수익을 내는 것 입니다.
- 상담 기간과 수익이 주어지며, 특정 상담을 수행하면 해당 상담 기간만큼의 날이 소요됩니다.
- 퇴사일 이후로 상담이 넘어가면
해당 상담은 수행할 수 없습니다. - 최대 수익을 구하기 위해 DP를 활용합니다.
문제 자체는 어렵지 않으나 점화식을 도출하는 과정이 까다롭습니다. 우리의 목표는 퇴사 전 최대 수익을 뽑는 것인데, 각 날짜에서 상담을 선택하거나 선택하지 않는 경우를 고려하고, 이전까지의 최적해를 활용하여 현재의 최적해를 구하는 동적 계획법의 특성을 잘 활용해야 합니다.
특히 상담이 걸리는 기간과 수익을 고려하면서 dp 배열에 각 날짜까지의 최대 수익을 저장하고, 이를 활용하여 최종적으로 퇴사일까지의 최대 수익을 구할 수 있습니다.
말 보다 그림으로 보는 것이 편하기 때문에..
위와 같이 각 날짜에서 최대 수익을 저장하는 DP 배열을 사용하여 예제 1번의 정답을 도출하는 과정을 살펴보겠습니다.
그 전에 정리하자면:
- i : 현재 날짜
- T[i] : i일에 시작하는 상담이 걸리는 기간
- i + T[i] : i일에 시작한 상담이 끝나고 난 다음 날
- P[i] : i일에 시작하는 상담의 수익
- dp[i] : i일까지 얻을 수 있는 최대 수익
1 일차 : 오늘(i일) 상담을 했을 때 상담이 끝나는 날의 최대 수익은, 그 날짜에 이미 계산된 수익과 (오늘까지의 최대 수익 + 오늘 상담 수익) 중 더 큰 값을 선택합니다.
2 일차 : 마찬가지로 오늘(2일) 상담을 했을 때 상담이 끝나는 날(7)의 최대 수익은, 7일차의 이미 계산된 수익과 (2일차까지의 최대 수익 + 오늘 상담 수익 : 20) 중 더 큰 값을 선택합니다.
3 일차 : 마찬가지로 오늘(3일) 상담을 했을 때 상담이 끝나는 날(4)의 최대 수익은, 4일차의 이미 계산된 수익과 (3일차까지의 최대 수익 + 오늘 상담 수익 : 10) 중 더 큰 값을 선택합니다.
4 일차 : 오늘(4일) 상담을 했을 때 상담이 끝나는 날(5)의 최대 수익은, 5일차의 이미 계산된 수익과 (4일차까지의 최대 수익 + 오늘 상담 수익 : 20) 중 더 큰 값을 선택합니다.
5 일차 : 오늘(5일) 상담을 했을 때 상담이 끝나는 날(7일)의 최대 수익을 계산합니다.
7일차에는 이미 2일차 상담으로 인한 수익 20만원이 저장되어 있습니다. 이것과 (5일차까지의 최대 수익 30만원 + 5일차 상담 수익 15만원 = 45만원)을 비교합니다. 45만원이 기존 값인 20만원보다 크므로 dp[7]은 45만원으로 업데이트됩니다.
6일차 : 6일차에 상담을 시작하면 상담이 끝나는 날은 10일(6 + 4)입니다. 따라서 이 상담은 퇴사일(8일)을 초과하기 때문에 선택할 수 없습니다. dp[10] = max(30 + 40, 45)와 같은 계산은 의미가 없습니다
즉, 문제의 핵심은 퇴사 전까지 최대의 수익을 내야하는 것이기 때문에, 오늘 상담했을 때 퇴사일을 넘어가지 않는 선에서 최대한 효율적인 상담을 해야합니다.
따라서 1일차부터, 상담이 끝났을 때 다음날의 최대 수익을 저장하고, 각 날짜에서 이미 계산된 최대 수익과 새로운 상담을 했을 때의 수익을 비교하면서 최적의 해를 찾아갑니다.
왜냐하면 같은 날짜에 도달할 수 있는 여러 가지 경우가 존재하기 때문입니다. 예를 들어 7일차에는:
- 2일차에 시작한 상담(5일 소요)으로 20만원을 벌 수 있고
- 5일차에 시작한 상담(2일 소요)과 이전 수익을 합쳐 45만원을 벌 수 있습니다.
이처럼 같은 날짜에 도달하더라도 어떤 상담들을 선택했는지에 따라 수익이 달라질 수 있으므로, 매번 최대값을 비교하고 저장하면서 최적의 해를 찾아가는 것입니다.
전체 코드
상담이 불가능한 경우(퇴사일을 초과한다면) 현재값(dp[i+1])과 이전까지의 최대 수익(dp[i]) 중 더 큰 값을 선택하여 최소한 이전까지의 최대 수익은 보장받을 수 있도록 합니다.
'Coding Test > 백준' 카테고리의 다른 글
| [백준, 11279번] 최대 힙 (우선순위 큐, Java) (0) | 2025.01.07 |
|---|---|
| [백준, 2193번] 이친수 (다이나믹 프로그래밍 : DP, Java) (0) | 2025.01.06 |
| [백준, 1927] 최소 힙 (우선순위 큐, Java) (1) | 2025.01.03 |
| [백준, 10844번] 쉬운 계단 수 (다이나믹 프로그래밍 : DP, Java) (2) | 2025.01.03 |
| [백준, 2156번] 포도주 시식 (다이나믹 프로그래밍 : DP, 동적 계획법 , Java) (2) | 2025.01.01 |
