인프런 커뮤니티 질문&답변

안녕하세요, 해당 문제를 풀다가 질문 사항이 있어서 질문드립니다.

import sys
sys.stdin = open("C:\\Study\\algorithm\\input.txt", "r")

def DFS(L, sum, time):
    global res
    if res[0] <= time <= m:
        if res[1] < sum:
            res[0] = time
            res[1] = sum
    for i in range(1, n+1):
        if time > m:
            break
        if ch[i] == 0:
            ch[i] = 1
            DFS(L+1, sum+ls[i-1][0], time+ls[i-1][1])
            ch[i] = 0


if __name__ == "__main__":
    n, m = map(int, input().split())
    ls = []
    ch = [0] * (n+1)
    res = [0] * 2
    for i in range(n):
        a, b = map(int, input().split())
        ls.append([a, b])
    DFS(0, 0, 0)
    print(res[1])

위 코드를 돌려보면 테스트 케이스 1,2번은 풀어지나 3번부터 timeOut이 뜨네요 (무한 루프가 도는거 같습니다)

이전 문제에서 알려주신 비슷한 방식으로
해당 문제를 1~n까지 DFS(n)전체를 탐색해서 최적의 점수를 도출할려고 했는데, 해당 유형의 문제가 나오면 이러한방식으론 해결이 불가능한걸까요?