2.휴가

휴가

 

카운셀러로 일하고 있는 현수는 오늘부터 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

 

문제풀이

import sys
sys.stdin=open("input.txt", "r")
def DFS(L,  sum): #L은 깊이이며, 날짜를 의미한다. 동시에 L은 인덱스임 
    global res
    if L == n+1:
      if sum > res:
            res = sum 
            print(sum)

    else:
      if L +T[L] <=n+1:             
            DFS(L+T[L], sum +P[L])   #상담을 수행한 후의 다음 날짜
      DFS(L+1, sum)    #+1씩 증가하다보면 n+1에서 걸림   #상담을 하지 않고 다음 날짜  
            
            

if __name__=="__main__":
    n = int(input())
    T=list()
    P=list()
    for _ in range(n):
        time, point =map(int, input().split())
        T.append(time)
        P.append(point)

    T.insert(0,0)
    P.insert(0,0)
  
    
    res = -2147000000
    DFS(1, 0) #DFS의 첫번째 요소는 깊이를 의미하는데, 시작이 0일수도 있고, 1일 수도 있다.

 

Hint

▶  T리스트는 "상담일수"의 리스트를 의미한다.

 

▶ P리스트는 "이익"리스트를 의미한다.

 

▶ L 은 깊이이며, 날짜(시점)을 의미한다. 

 

▶ T[L]  :  상담일수를 의미한다. 

 

▶ L + T[L] : 상담을 수행한 후의 "다음 날짜" 

 

▶ if문에서 L +T[L] <=n+1:         

     → n+1인 이유

     →n이 7인 경우 현수는 n +1인 8일에 휴가를 떠난다. 

     →L +T[L]이 상담을 수행 후의 "다음 날짜"

     →현수는 최대한으로 상담을 후행한 후에 n+1되는 날에는 휴가를 가야하기 때문이다.