[Algorithm] 휴가 (DFS) (⭐부분집합과 조합의 차이)

부분집합과 조합의 차이가 약간 헷갈리지만.. 아래 코드를 보면 둘은 큰 차이가 없다. 조합이 for i in range(s, n+1): 이렇게 가지를 뻗어나가는 코드가 있다는 것?! 정도의 차이이다.

그래프를 실제 그려보니 조합과 부분집합이 조금은 구분이 된다.

---

방법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)

방법2) 부분집합

def DFS(L, sum):
    global max

    if L == (n+1):
        if sum > max:
            max = sum
    else:
        if L+T[L] <= (n+1):
            DFS(L+T[L], sum+P[L])  # 상담을 했을 때
        DFS(L+1, sum)  # 1씩 증가하다보면 n+1로 가게 됨

n = int(input())
T = list()
P = list()
for _ in range(n):
    a, b = map(int, input().split())
    T.append(a)
    P.append(b)

max = -2147000000
T.insert(0, 0)  # 인덱스 번호를 1일부터 맞추기 위해 한 칸씩 미루기
P.insert(0, 0)  # 인덱스 번호를 1일부터 맞추기 위해 한 칸씩 미루기
DFS(1, 0)  # 날짜, 돈 합
print(max)