인프런 커뮤니티 질문&답변
작성한 질문수
조합
작성
·
229
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)
답변 1
1
김태원
지식공유자
안녕하세요^^
조합을 이용해서 모든 부분집합을 확인하는 형태로 짜시려면 아래 코드처럼 답을 구하는 지점이 명확해야 할 것 같습니다.
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))