-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
조합으로 구하면 안되나요?
22.03.09 12:15 작성 조회수 150
0
선생님 이 문제 부분집합으로 푸셨는데, 조합으로 구하면 안되나요? 부분집합과 조합의 차이가 무엇인가요?
아래처럼 조합으로 코드 짰는데 선생님께서 푸신 답변과 비슷한듯 다르네요.
for i in range(s, n+1)을 없이 푸셨는데... 조합에서는 필요하지 않나요?
def DFS(s, money):
global max
if s > (n+1):
return
if s == (n+1):
if money > max:
max = money
for i in range(s, n+1):
if i+graph[i][0] <= (n+1):
DFS(i+graph[i][0], money+graph[i][1])
DFS(i+1, money)
n = int(input())
graph = []
for _ in range(n):
a, b = map(int, input().split())
graph.append([a, b])
graph.insert(0, [0, 0])
max = -2147000000
DFS(1, 0)
print(max)
답변을 작성해보세요.
0
답변 1