[백준] 일곱 난쟁이

문제

https://www.acmicpc.net/problem/2309

TC

DFS를 인접 행렬로 구현했다면 O(N^2)
DFS를 인접 리스트로 구현했다면 O(V+E)

Idea

Python의 경우 combinations를 사용하면 쉽게 풀리지만, DFS를 공부중인 만큼 DFS로 풀어보았다.
9명의 난쟁이 중 7명의 난쟁이를 DFS로 선택하면서 선택된 7명의 난쟁이의 키 합이 100이라면
오름차순으로 정렬 후에 출력해주면 된다.

가능한 1가지 조합만 나오면 되기에, sum(s) == 100을 만족한다면, 출력해주고 exit()으로 해당 함수를 빠져나왔다.

code (Python)

def dfs(cnt, start):
    # 7명의 난쟁이가 선택됐고 합이 100이면
    if cnt == 7:
        if sum(s) == 100:
            # 오름차순으로 정렬해서 출력
            for i in sorted(s):
                print(i)
            # 가능한 정답이 한 가지라도 나왔으면 종료하기
            exit()
        # 7명의 난쟁이의 합이 100이 아니면 해당 경우의 수가 아님
        else:
            return

    for i in range(start, 9):
        s.append(heights[i])
        dfs(cnt+1, i+1)
        s.pop()

# 난쟁이들의 키
heights = [int(input()) for _ in range(9)]

s = []
dfs(0, 0)

self code review

"틀렸습니다"를 생각보다 많이봐서 당황했던 문제...
7명의 가능한 조합이 한 번이라도 나왔으면 빠져나와야 했지만, 이 부분을 놓쳐서 조금 헤매었다.