백준 2309 일곱 난쟁이 (파이썬)

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

2309번: 일곱 난쟁이

1. 입력받은 난쟁이의 키를 a에 저장한다

2. dfs 조합으로 난쟁이 9명 중 7명을 선택한다

3. 7명을 선택하면 키를 더하여 res에 저장하고 각 난쟁이의 키를 ans에 저장한다

4. res가 100이면 ans를 정렬하고 순서대로 출력한 후 끝낸다

import sys

input = sys.stdin.readline

def dfs(cnt, idx):
    if cnt == 7:
        res, ans = 0, []
        for i in range(9):
            if select[i]:
                res += a[i]
                ans.append(a[i])
        if res == 100:
            ans.sort()
            for s in ans:
                print(s)
            sys.exit()
        return

    for i in range(idx, 9):
        select[i] = 1
        dfs(cnt + 1, i + 1)
        select[i] = 0


a = []
for _ in range(9):
    a.append(int(input()))

select = [0 for _ in range(9)]
dfs(0, 0)