📌 문제 요약

• 문제 이름: 2309번: 일곱 난쟁이
• 알고리즘 분류: 브루트포스 알고리즘, 정렬, 백트래킹 (DFS)
• 사용 언어: Python 3

아홉 명의 난쟁이 중 진짜 일곱 난쟁이를 찾아야 합니다. 진짜 일곱 난쟁이의 키의 합은 정확히 100입니다. 아홉 난쟁이의 키가 주어졌을 때, 진짜 일곱 난쟁이의 키를 오름차순으로 출력하는 문제입니다.

💡 문제 접근 방법 (핵심 로직)

서로 다른 9명 중 순서에 상관없이 7명을 뽑는 조합(Combination) 문제입니다. 파이썬의 itertools.combinations 라이브러리를 사용하면 아주 쉽게 풀 수 있지만, 알고리즘 역량을 기르기 위해 DFS를 활용한 백트래킹(Backtracking) 기법으로 직접 조합을 구현했습니다.

1. 사전 정렬: 출력 조건이 '오름차순 정렬'이므로, 처음에 입력받은 배열을 먼저 .sort() 해줍니다.
2. 상태 공간 트리 탐색 (DFS): visited라는 배열을 스택처럼 활용합니다.
3. 백트래킹 로직:
   • visited에 현재 난쟁이를 넣습니다 (append).
   • 다음 난쟁이를 찾기 위해 재귀 함수를 호출합니다 (dfs(i + 1)).
   • 탐색을 마치고 돌아오면, 넣었던 난쟁이를 다시 빼서 원래 상태로 되돌립니다 (pop). 이렇게 해야 다른 경우의 수를 탐색할 수 있습니다.
4. 종료 조건 (Base Case): visited의 길이가 7이 되면 합을 검사합니다. 합이 100이면 그대로 원소들을 출력하고 프로그램 자체를 종료(exit())합니다.

💻 코드 구현

import sys
input = sys.stdin.readline

arr = [int(input()) for _ in range(9)]
arr.sort()

visited = []

def dfs(start_node):
    # 7명을 모두 뽑았을 때
    if len(visited) == 7:
        # 키의 합이 100인지 확인
        if sum(visited) == 100:
            for j in visited:
                print(j)
            exit() # 정답을 찾으면 즉시 전체 프로그램 종료
        return
    
    # 백트래킹을 이용한 조합 탐색
    for i in range(start_node, 9):
        visited.append(arr[i])
        dfs(i + 1)
        visited.pop()

dfs(0)

---

## 💡 [추가 풀이] 파이썬다운 우아한 해결: `itertools.combinations`

알고리즘의 뼈대(DFS)를 이해했다면, 실제 코딩 테스트나 실무에서는 파이썬이 제공하는 강력한 표준 라이브러리인 `itertools.combinations`를 활용하는 것이 훨씬 빠르고 효율적입니다. 중첩 반복문이나 재귀 함수 없이 단 몇 줄만으로 조합(Combination)을 완벽하게 구현할 수 있습니다.

### 방법 1: 직관적으로 진짜 난쟁이 7명 뽑기 ($9C_7$)
가장 직관적으로 9명 중 7명을 뽑는 모든 경우의 수를 탐색하는 방법입니다.

```python
import sys
from itertools import combinations
input = sys.stdin.readline

arr = [int(input()) for _ in range(9)]
arr.sort() # 오름차순 출력을 위한 사전 정렬

# 9명 중 7명을 뽑는 모든 조합(comb)을 하나씩 확인
for comb in combinations(arr, 7):
    # 뽑은 7명의 키 합이 100이라면
    if sum(comb) == 100:
        for height in comb:
            print(height)
        break # 정답을 찾았으므로 즉시 루프 종료

방법 2: 발상의 전환, 가짜 난쟁이 2명 빼기 ($9C_2$)

알고리즘의 로직을 살짝 비틀어, "전체 합에서 가짜 난쟁이 2명의 키를 뺐을 때 100이 남는가?"로 접근하는 방법입니다. 탐색 횟수는 36번으로 동일하지만, 합산 연산이 줄어들고 리스트 컴프리헨션(List Comprehension)을 활용하여 코드를 더욱 파이썬답게(Pythonic) 작성할 수 있습니다.

import sys
from itertools import combinations
input = sys.stdin.readline

arr = [int(input()) for _ in range(9)]
arr.sort()
total_sum = sum(arr) # 9명 전체 키의 합

# 9명 중 가짜 난쟁이 2명을 뽑는 조합 탐색
for fake in combinations(arr, 2):
    # 전체 합에서 가짜 2명의 키를 뺐을 때 100이 된다면
    if total_sum - sum(fake) == 100:
        # 전체 배열에서 가짜 2명을 제외한 진짜 난쟁이들만 리스트 컴프리헨션으로 추출
        real_dwarfs = [d for d in arr if d not in fake]
        
        for height in real_dwarfs:
            print(height)
        break