55.휴가(DFS활용)
카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들어 휴가를 떠나려 한다.
현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다.
각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다.
만약 N = 7이고, 아래와 같이 예약이 잡혔있다면
1일 2일 3일 4일 5일 6일 7일
T 4 2 3 3 2 2 1
P 20 10 15 20 30 20 10
1일에 잡혀있는 상담은 총 4일이 걸리며, 상담했을 때 받을 수 있는 금액은 20이다. 만약 1일에 예약된 상담을 하면 4일까지는 상담을 할 수가 없다.
하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을 혼자 할 수없어 최대 이익이 나는 상담 스케쥴을 짜기로 했다.
휴가를 떠나기 전에 할 수 있는 상담의 최대 이익은 1일, 5일, 7일에 있는 상담을 하는 것이며, 이때의 이익은 20+30+10=60이다.
현수가 휴가를 가기 위해 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
▣ 입력설명
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 1일부터 N일까지 순서대로 주어진다. (1 ≤ T ≤ 7, 1 ≤ P ≤ 100)
▣ 출력설명
첫째 줄에 현수가 얻을 수 있는 최대 이익을 출력한다.
▣ 입력예제 1
7 4
20
2 10
3 15
3 20
2 30
2 20
1 10
▣ 출력예제 1
60
내 코드
def dfs(s,v,sum):
global profit
if v>n:
return
if profit<sum:
profit=sum
for i in range(s,n):
dfs(i+lst[i][0],v+lst[i][0],sum+lst[i][1])
n=int(input())
lst=[tuple(map(int,input().split())) for _ in range(n)]
profit=-int(1e10)
dfs(0,1,0)
print(profit)s로 반복문의 시작지점, v로 날짜를 설정했는데 반복문이 순차적으로 더해서 그런건지 sum에서 이상한 답이 나왔다.
풀이
def DFS(L, sum):
global res
if L==n+1:
if sum>res:
res=sum
else:
if L+T[L]<=n+1:
DFS(L+T[L], sum+P[L])
DFS(L+1, sum)
if __name__=="__main__":
n=int(input())
T=list()
P=list()
for i in range(n):
a, b=map(int, input().split())
T.append(a)
P.append(b)
res=-2147000000
T.insert(0, 0)
P.insert(0, 0)
DFS(1, 0)
print(res)반성점
- 비슷한 유형의 문제가 계속 나오는데 매번 틀린다.
배운 것
- N일까지 끝내야 한다면 제한 범위는 N+1까지(<=)
- 순차적으로 더하는 것이 아니라 건너뛰어야 할 때는 반복문 대신 if문으로 해당될 때와 안 될 때를 나눈다.
