• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    해결됨

오류 부분

21.01.18 14:43 작성 조회수 105

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)
course-thumbnail

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

1. 최대점수 구하기(DFS)

강의실 바로가기

답변 1

답변을 작성해보세요.

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)

이 글과 비슷한 Q&A