[DFS활용] - 휴가

휴가

 

카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동 안 최대한 많은 상담을 해서 휴가비를 넉넉히

만들어 휴가를 떠나려 한다.
현수가 다니는 회사에 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다.
각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이 루어져 있다.

만약 N = 7이고, 아래와 같이 예약이 잡혔있다면

 

 

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(day,summ):
    global M
    if day>n:
        if M<summ:
            M=summ
    else:
        DFS(day+dayS[day],summ+PointS[day])
        DFS(day+1,summ)


n=int(input())
dayS=[0]
PointS=[0]
for _ in range(n):
    a,b=map(int,input().split())
    dayS.append(a)
    PointS.append(b)
M=0
DFS(1,0)


print(M)

전형 적인 선택을 하냐 마냐로 탐색을 시작하는 DFS활용 문제이다.

선택을 할경우 day의 해당 인덱스만큼 증가를 시키고 점수 또한 더 한다.

선택을 안할 경우 day는 +1(다음날)로 가며 점수는 더하지 않는다.

 

+) 아.. 잘못 푼 문제이다..! 종료 조건을 착각하였다.

[*  7일에 1일이 걸려 일을 할수 있으면 7+1인 8이 종료 조건이다. *]

 

해당 로직은 맞지만종료 조건이 day==n+1이 되어야 하며 이보다 큰 day는 return으로 반환을 해야한다.

 

def DFS(day,summ):
    
    global M
    if day>n+1:
        return
    if day==n+1:
        if M<summ:
            M=summ
    else:
        DFS(day+dayS[day],summ+PointS[day])
        DFS(day+1,summ)

 

 

정답 코드

import sys
sys.stdin=open("input.txt", "r")
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)

 

나와 같은 접근을 하였지만

DFS의 조건이 다르며 조건 또한 else구문에서 처리가 되어 있다.