2309. 일곱 난쟁이

TLDR

Combination을 사용하면 된다. itertools.combinations 사용하면 금방 풂.

itertools.combinations(iterable, r)

---

Snippet

"""
http://boj.kr/2309

9명의 난쟁이 중에서 7명을 뽑았을때 합이 100이면 리턴하는 문제. Combination

[itertools.combinations](https://docs.python.org/3/library/itertools.html#itertools.combinations) 참고
"""

from collections.abc import Sequence
# from itertools import combinations

def combinations(iterable, r):
    # combinations('ABCD', 2) → AB AC AD BC BD CD
    # combinations(range(4), 3) → 012 013 023 123

    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))

    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)



def main(seq: Sequence[int]) -> tuple[int]:
    for comb in combinations(seq, 7):
        if sum(comb) == 100:
            return sorted(comb)
    return tuple()


if __name__ == "__main__":
    seq = [int(input()) for _ in range(9)]
    print("\n".join(str(x) for x in main(seq)))

---

Sample Input & Expected Output

Input

20
7
23
19
10
15
25
8
13

Expected Output

7
8
10
13
19
20
23

---

Notes

itertools combinations 분석