Section 7-1) 최대점수 구하기(DFS)

안녕하세요 강사님, 질 좋은 강의 제공해주셔서 감사합니다. 아래 첨부한 제 코드로 진행하면 DFS(L+1, sum+s[L], time+t[L]) 에서 list list index out of range 에러가 뜹니다. 강사님은 아래와 같이 푸셨던데, 제 코드에서 어떠한 점이 에러를 반환했을까요?

if L==n:
    if sum>answer: 
        answer=sum

import sys 
sys.stdin=open("input.txt","r") 

def DFS(L, sum, time): 
    global answer 
    if time>m: 
        return 
    if L==n and sum>answer: 
        answer=sum 
    else: 
        DFS(L+1, sum+s[L], time+t[L]) 
        DFS(L+1, sum, time) 
        
n,m=map(int, input().split()) 
s=list() 
t=list() 
for i in range(n): 
    ss,tt=map(int,input().split()) 
    s.append(ss) 
    t.append(tt) 
answer=0 
DFS(0,0,0) 
print(answer)

안녕하세요, 인프런 AI 인턴입니다.

님의 코드에서 발생한 ‘list index out of range’ 에러는 리스트 s와 t에 접근할 때, 인덱스 L이 리스트의 범위를 벗어났기 때문에 발생합니다. 에러 메시지가 나타나는 부분은 DFS(L+1, sum+s[L], time+t[L]) 호출 시점인데요, 이는 L이 n과 같아지는 순간, 즉 L이 리스트 s와 t의 마지막 인덱스를 넘어섰을 때 발생합니다.

강사님이 제시한 해결 방법에서는 if L==n: 조건을 통해 재귀 호출을 종료하게 됩니다. 이 로직은 L이 n에 도달했을 때, 즉 모든 문제를 다 고려했을 때를 의미하며, 이 경우 더 이상 리스트 s와 t에 접근하지 않고 재귀 호출을 종료하도록 설계되어 있습니다.

따라서, 님의 코드에서도 이와 같은 조건을 추가해주어야 합니다. 즉, DFS함수 내부에서 L이 n에 도달했을 때를 체크하는 조건문을 통해 더 이상 리스트에 접근하지 않도록 해야 합니다. 이미 조건문으로 if L==n:을 사용하고 계시니, 이 때 sum과 answer를 비교하는 로직은 올바르게 작성하셨습니다. 문제는 DFS(L+1, sum+s[L], time+t[L])과 DFS(L+1, sum, time) 호출을 할 때, L<n일 때만 실행되도록 조건을 수정해주어야 합니다. 예를 들어, 다음과 같이 조건문 내에 재귀 호출을 넣어주는 것입니다.

if L<n: # L이 n보다 작을 때만 재귀 호출 실행
    DFS(L+1, sum+s[L], time+t[L])
    DFS(L+1, sum, time)

이러한 방식으로 코드를 수정하면, L이 n과 같아져 리스트의 범위를 벗어나려고 할 때 재귀 호출을 하지 않으므로 ‘list index out of range’ 에러를 해결할 수 있습니다.

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