1. 문제 해석
남은 N일 동안 최대한 많은 이익을 얻기 위해 상담을 계획하고 있다. 각 상담은 완료하는 데 일정 기간이 소요되며, 해당 기간 동안 다른 상담을 진행할 수 없고 얻을 수 있는 최대 수익을 계산하는 문제이다.
예를 들어, N=7일 때, 상담 일정이 다음과 같다고 가정하자:
1일차 상담: 3일 소요, 10의 수익
4일차 상담: 1일 소요, 20의 수익
5일차 상담: 2일 소요, 15의 수익
상담이 다른 상담을 진행할 수 있는 기간과 겹치지 않게 스케줄을 짜야 하며, N+1일째 되는 날에는 퇴사 예정이므로 그 전까지 모든 상담이 마무리되어야 한다.
2. 문제 접근
N의 범위가 N (1 ≤ N ≤ 15)이 주어졌고, 시간제한은 2초이기 때문에 어떤 알고리즘을 이용해도 여유로워 보였다. 이럴 경우 DP 혹은, 오랜시간이 걸리더라도 가장 확실한 답이 나오는 브루트 포스를 사용할 수 있다.
나는 후자를 사용했지만, DP를 사용하는 방법도 소개해 보려고 한다.
3. 알고리즘 풀이
- 트리형태로 상담을 선택했을 때와 선택하지 않았을 때를 나눔
- 종료 조건 : day가 N이상이 된다면 멈추고, 최대 수익으로 갱신
이는 이전에 작성했던 스타트와 링크 알고리즘 풀이와 유사하다.
1번을 1일차 상담을 선택할 경우와 안할 경우를 나눈다. 마찬가지로 2번과 3번도 나누어 간다.
depth가 N이상이 되었을 때는 더 이상 불가능 하기에 return한다.
N=int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
ans=0
#day는 현재 날짜, profit은 현재까지의 수익
def dfs(day,profit):
global ans # 전역 변수 ans 사용
# 현재 날짜가 상담 가능 일수 N을 넘으면 현재까지의 수익을 최대 수익과 비교
if day >= N:
ans=max(ans,profit) # 최대 수익 갱신
return
# 상담 완료 날짜가 N을 넘지 않으면 상담 진행
if day+arr[day][0] <= N:
dfs(day+arr[day][0],profit+arr[day][1])
# 상담을 선택하지 않을 경우, 다음 날짜로 넘어감
dfs(day+1,profit)
# 초기 날짜(0)와 수익(0)으로 DFS 탐색 시작
dfs(0,0)
# 최대 수익 출력
print(ans)dfs(day+1,profit) 상담을 선택하지 않았을 경우는 날짜만 지나기 때문에 이처럼 작성했다.
(2) DP를 이용한 다른 풀이
- 날짜를 뒤에서 부터 세면서 DP를 이용한다.
- dp[0]이 최대 이익이 된다.
N=int(input())
T=[0]*N
P=[0]*N
dp=[0]*(N+1)
for i in range(N):
T[i], P[i] = map(int,input().split())
# 뒤에서부터 탐색을 시작하여 각 일자에서 얻을 수 있는 최대 이익을 dp 리스트에 저장
for i in range(N-1,-1,-1):
# 만약 상담을 시작하면 N일 내에 완료 가능한 경우
if i+T[i]<=N:
# 현재 상담을 선택하는 경우와 선택하지 않는 경우 중 더 큰 이익을 최대 이익으로 결정
dp[i]=max(dp[i+1],dp[i+T[i]]+P[i])
else:
# 현재 상담을 완료할 수 없는 경우, 현재 일자의 최대 이익은 다음 날과 같다
dp[i]=dp[i+1]
# 최종적으로 0일차에서의 최대 이익 출력
print(dp[0])
이 풀이에서는 DP를 사용했다.
스타트와 링크 문제와 유사한 알고리즘으로 해결이 가능하지만, DP를 이용하는 것이 신박해서 다시 한 번 기록해봤다.
Slow-starter