-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
오류 부분
21.01.18 14:43 작성 조회수 108
0
안녕하세요! 선생님의 강의 들으며 많은 도움 얻고 있습니다 ^^ 다름이 아니라 제가 짠 코드에서 in1, in2, in3 까지는 답이 맞는데, in4부분 부터는 index out of range 오류가 나서 res의 길이를 더 늘려주면(원래는 res=[0]*n 이었는데 res[0]*(n+100)으로 늘려줬습니다), 답이 0으로만 출력됩니다. 혹시 어떤 부분이 잘못된 것일까요?
혼자 오래 고민해 보았지만 그럼에도 도저히 어떻게 손을 대야할 지 갈피가 잡히지 않아 질문을 남깁니다..! ㅠㅠ
import sys
sys.stdin=open('input.txt', 'rt')
def DFS(x,s,time) :
global xx
if time>m:
return
if time==m :
if sum(res) > xx:
xx=sum(res)
return
else :
for i in range(s,n+1) :
res[x]=a[i-1][0]
DFS(x+1, i+1, time+a[i-1][1])
res[x]=0
if __name__=='__main__' :
a=[]
n, m = map(int, input().split())
for _ in range(n) :
a.append(list(map(int, input().split())))
xx=0
res=[0]*(n+100)
DFS(0,0,0)
print(xx)
답변을 작성해보세요.
1
김태원
지식공유자2021.01.20
안녕하세요^^
if time==m: 이 조건이 문제입니다. 꼭 시간이 m일때만 답이 되는게 아닙니다. 제한시간 m안에 얻은 점수도 답이 될 수 있습니다. 4번 같은 경우는 time==m되는 경우가 존재하지 않기 때문에 0이 출력되는 것입니다.
위에 코드처럼 조합 방식으로 하고 싶다면
import sys
#sys.stdin=open('in4.txt', 'rt')
def DFS(x,s,time) :
global xx
if time>m:
return
if(sum(res)>xx):
xx=sum(res)
for i in range(s, n):
res[x]=a[i][0]
DFS(x+1, i+1, time+a[i][1])
res[x]=0
if __name__=='__main__' :
a=[]
n, m = map(int, input().split())
for _ in range(n) :
a.append(list(map(int, input().split())))
xx=0
res=[0]*n
DFS(0,0,0)
print(xx)
답변 1