Algorithm - 휴가(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[휴가(DFS)]

 

카운셀러로 일하고 있는 현수는 오늘부터 N+1일째 되는 날 휴가를 가기 위해서, 남은 N일 동안 최대한 많은 상담을 해서 휴가비를 넉넉히 만들고자 한다. 현수가 다니는 회사에는 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다.

참고로, 각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져 있다.

 

만약 N = 7이고, 아래와 같이 예약이 잡혔다면 1일에 잡혀있는 상담은 총 4일이 걸리며 상담을 했을 때 받을 수 있는 금액은 20이다. 또한, 1일에 예약된 상담을 하면 4일까지는 상담을 할 수 없다.

 

상담 일정

 

하나의 상담이 하루를 넘어가는 경우가 많기 때문에 현수는 예약된 모든 상담을 혼자할 수 없어 최대이익이 나는 상담 스케줄을 짜기로 했다. 현수가 휴가를 가기 위해 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에 N(1 ≤ N ≤ 15)이 주어진다.

두 번째 줄부터는 N일이 순서대로 주어진다.

(단, 1 ≤ T ≤ 7, 1 ≤ P ≤ 100) 

 

*출력 설명

첫 번째 줄에 현수가 얻을 수 있는 최대 이익을 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_57.txt', 'rt')

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)
    
# 출력 : 60

 

input_57.txt(입력)

7
4 20
2 10
3 15
3 20 
2 30 
2 20 
1 10

 

 

중요내용

1. 변수 T는 상담하는데 걸리는 시간을 저장하는 리스트이다.
2. 변수 P는 상담수익을 저장하는 리스트이다.
3. T와 P의 인덱스 번호를 상담 날짜와 맞추기 위해, insert() 함수를 사용하여 각 리스트의 0번 인덱스 자리에 0의 값을 넣어준 것이다.
4. DFS() 함수의 인자 L은 T와 P 리스트에 접근하는 인덱스 번호이자 동시에 상담 날짜를 의미한다.
5. DFS () 함수의 인자 sum은 상담의 최대 수익을 의미한다.
6. DFS(L+T[L], sum+P[L]) 코드는 해당 날짜의 상담을 하는 경우를 의미한다.
7. DFS(L+1, sum) 코드는 해당 날짜의 상담을 하지 않고 다음날로 넘어가는 경우를 의미한다.
8. if절의 조건 " L+T[L] <= n+1 "은 현재 상담을 마치고 난 후의 시점이 휴가를 가는 시점보다 늦어서는 안된다는 것을 의미한다.