풀이 전략은 다음과 같습니다.
이 문제는 DP 알고리즘 문제입니다.
DP 알고리즘 문제임을 어떻게 알아챌 수 있나요?
최대 이익을 구하기 위해선, 1일부터 N일까지 가능한 모든 상담일 조합을 계산하여 최대값을 구해야 합니다.
(금액) / (소요기간)이 높은 순서대로 상담일을 배정하는 것이 최대 이익을 보장할까요?
아닙니다. 모든 상담일 조합을 다 계산해봐야 최대 이익을 구할 수 있습니다.
따라서 이 문제는 그리디 알고리즘이 아닙니다.
그럼 어떻게 모든 상담일 조합을 다 계산해볼 수 있을까요?
이런 상황에서 쓰는 알고리즘이 바로 DP 알고리즘입니다.
DP 알고리즘은 모든 부분 문제들을 해결하여 최적해를 찾습니다.
DP 배열에 부분 문제의 최적해를 저장하고,
배열에 저장된 부분 문제의 최적해와 새로운 케이스의 해를 비교하여 더 큰 크기의 부분 문제의 최적해를 구해가기 때문에 모든 부분 문제를 다 비교할 수 있습니다.
따라서 DP 알고리즘은 부분 문제 간의 함축적 순서를 이용하여 문제를 해결하기 때문에,
모든 조합을 다 고려해야 하는 문제라면 DP 알고리즘을 떠올리는 것이 좋습니다.
풀이 단계는 다음과 같습니다.
- 바깥쪽 루프: 0부터 N-1까지 순회합니다.
- 안쪽 루프: i 일에 상담을 진행할 수도 있고, 안 할수도 있겠죠?
<i일 상담이 끝난 다음 날>부터 <마지막 날>까지 돌면서
i일에 상담을 안한 경우의 수익(dp[j])과 i일에 상담을 한 경우의 수익(dp[i] + i일 상담의 금액)을 비교하여 더 큰 값을 dp[j]에 저장합니다.
만약 dp[j]에dp[i] + i일 상담의 금액이 저장됐다면, 적어도 j일까지는 최대 수익을 위해선 i일에 상담을 해야한다는 의미가 되겠습니다.
N = int(input()) # 퇴사까지 남은 일수
schedule = [list(map(int, input().split())) for i in range(N)] # [소요일수, 비용]
dp = [0 for i in range(N+1)] # dp[i]: i일까지의 최대 수익
for i in range(N):
for j in range(i+schedule[i][0], N+1):
if dp[j] < dp[i] + schedule[i][1]: # i번째 날에 상담을 진행할 경우 수익이 더 높다면
dp[j] = dp[i] + schedule[i][1] # i번째 날에 상담 진행
print(dp[-1])이해를 위해서 예시를 따라가보겠습니다.
먼저 dp배열을 0으로 초기화해줍니다.
이제 위의 표를 따라가며 dp 배열을 채워볼까요?
1일에 상담 진행 ->
1일 상담이 끝난 4일에서 7일까지는 1일차 상담 금액이 누적됨.
0 < 10 이므로 dp[3] ~ dp[6]에 10 저장
2일에 상담 진행 ->
2일 상담이 끝난 7일에는 2일차 상담 금액이 누적됨.
이때 10 < 20 이므로, 7일차의 최대 수익을 위해선 1일이 아닌 2일에 상담을 진행해야함.
따라서 dp[6]에 20 저장
3일에 상담 진행 ->
3일 상담이 끝난 4일에서 7일까지는 3일차 상담 금액이 누적됨.
이때 4일, 5일, 6일은 10 = 10이므로 상담을 1일차에 진행해도 좋고, 3일차에 진행해도 좋음.
7일은 20 > 10 이므로, 7일차의 최대 수익을 위해선 3일이 아닌 2일에 상담을 진행해야 함.
따라서 dp값 변동 없음.
4일에 상담 진행 ->
4일 상담이 끝난 5일에서 7일에는 4일차 상담 금액이 누적됨.
5일, 6일은 10 < 10 + 20 이므로, 최대 수익을 위해선 1일(혹은 3일)만이 아닌 1일 + 4일에 상담을 진행해야 함. ( 4일 상담 전까지의 최대 수익 + 4일차 상담 금액 = 1일차 상담금액 + 4일차 상담금액 = 10 + 20 )
7일도 20 < 10 + 20 이므로, 2일이 아닌 1일 + 4일에 상담을 진행해야 함.
따라서 dp[4] ~ dp[6]에 30 저장
5일에 상담 진행 ->
5일 상담이 끝난 7일에는 5일차 상담 금액이 누적됨.
7일은 30 < 30 + 15이므로, 1일 + 4일만이 아닌 1일 + 4일 + 5일에 상담을 진행해야 함. (dp[4] + 5일차 상담 금액 = 30 + 15)
따라서 dp[6]에 45 저장
6일, 7일에 상담 진행 ->
상담이 끝난 날이 N일 이후 이후이므로 6일차와 7일차의 상담 금액이 누적되는 날짜가 없음. 따라서 dp 배열이 업데이트되지 않음.
이렇게 dp[6] = 45가 저장되어 답은 45가 됩니다.
두번의 루프를 돌기 때문에 모든 부분 문제의 최적해를 구하며
최종 문제의 최적해를 구할 수 있습니다.
DP 알고리즘임을 알아채는 것이 중요했던 문제로 보입니다.
