[인프런] 휴가

문제

• 오늘부터 N+1일째 되는 날 휴가를 가기 위해, 남은 N일동안 최대한 많은 상담을 하여 휴가비를 넉넉히 만들어 휴가를 떠나려 한다.
• 하루에 하나씩 서로 다른 사람의 상담이 예약되어 있다.
• 각각의 상담은 상담을 완료하는데 걸리는 날수 T와 상담을 했을 때 받을 수 있는 금액 P로 이루어져있다.
• 휴가를 가기 위해 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하라.

입력

• n (1 <= N <= 15): 휴가를 가기 전까지 상담을 위해 주어진 날짜
• T (1 <= T <= 7): 상담 완료하는데 걸리는 날수
• P (1 <= P <= 100): 상담을 했을 때 받을 수 있는 금액

입력 예제

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

출력 예제

60

생각 포인트

• 상담을 한다, 하지 않는다로 구분되며 가장 휴가비를 많이 받을 수 있는 경우를 탐색하기 위해 DFS로 푼다.
• 함수의 종료 조건은 노드의 level이 n과 같아질 때이다.
• 상담을 할때와 상담을 하지 않을때를 구분하여 적절하게 함수에 인자를 넘겨준다.

Solution

n = int(input())
time = list()
pay = list()
ret = -2147000000


for _ in range(n):
    t, p = map(int, input().split())
    time.append(t)
    pay.append(p)


def dfs(level, sum):
    global ret

    if level == n:
        if sum > ret:
            ret = sum
    else:
        if level + time[level] <= n:
            dfs(level + time[level], sum + pay[level])
        dfs(level + 1, sum)


dfs(0, 0)
print(ret)