• 카테고리

    질문 & 답변

  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

조합

21.01.14 20:16 작성 조회수 134

0

조합처럼 이렇게 풀었는데 in1,in2까지는 정답이 잘 맞는데 그 이후에는 답이 틀리게 나옵니다. 어떤 부분이 잘못되었을까요?

def DFS(s, time, score):

    global res

    if time>m :

        if score-a[s-1][0]>res:

            # print("score %d" %(score-a[s-1][0]))

            res=score-a[s-1][0]

    else:

        for i in range(s, n):

            DFS(i+1,time+a[i][1],score+a[i][0])

n, m=map(int, input().split())

a=[]

for i in range(n):

    x1,x2 = map(int, input().split())

    a.append((x1,x2))

res=0

DFS(0,0,0)

print(res)

course-thumbnail

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

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

강의실 바로가기

답변 1

답변을 작성해보세요.

1

김태원님의 프로필

김태원

지식공유자

2021.01.15

안녕하세요^^

조합을 이용해서 모든 부분집합을 확인하는 형태로 짜시려면 아래 코드처럼 답을 구하는 지점이 명확해야 할 것 같습니다.

def DFS(s, time, score):
    if(time>m):
        return
    global res
    if time<=m:
        if(score>res):
            res=score;
    for i in range(s, n):
        DFS(i+1,time+a[i][1],score+a[i][0])

n, m=map(int, input().split())

a=[]

for i in range(n):

    x1,x2 = map(int, input().split())

    a.append((x1,x2))

이 글과 비슷한 Q&A