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

Question

안녕하세요 강사님, 질 좋은 강의 제공해주셔서 감사합니다.  아래 첨부한 제 코드로 진행하면 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 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 님의 코드에서 발생한 &lsquo;list index out of range&rsquo; 에러는 리스트 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 과 같아져 리스트의 범위를 벗어나려고 할 때 재귀 호출을 하지 않으므로 &lsquo;list index out of range&rsquo; 에러를 해결할 수 있습니다.