休暇(DFS)

深度/幅優先ナビゲーション(DFS、BFS)による

に質問

休暇（三星ソフトウェア能力評価提出問題：DFS使用）

ヒョンス氏はコンサルタントで、今日からN＋1日の休暇を取るため、残りのN日にできるだけ多くの問い合わせを行い、休暇費用を十分に支払うために休暇を取る準備をしている.
賢洙が勤めている会社は毎日違う人の相談を予約している.
各カウンセリングは,カウンセリング完了に要する日数Tと,カウンセリング時に得られる金額Pからなる.
N=7の場合、以下のように予約されます.

1日に決めた問い合わせは全部で4日かかり、問い合わせの際に受け取れる金額は20です.万一
4日までに予定の打ち合わせをすれば、打ち合わせはできません.
1つのコンサルティングが1日を超えることが多いため、賢洙は一人ですべての予定のコンサルティングを完了することができる.
いいえ、最大利益のコンサルティング日程を手配することにしました.
休暇前に相談する最大のメリットは、1日、5日、7日に相談することです.
このときの利益は20+30+10=60です.
賢洙の休暇で得られる最大の収益を求めるプログラムを作成してください.
■説明の入力
第1行はN(1≦N≦15)を与える.
2行目から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", "rt")     # read text

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)

リファレンス

インフラストラクチャ:Pythonアルゴリズム回答