백준 2309번 문제해결 : 조합 , 완전탐색 알고리즘

1. 문제 분석

📌 문제 한 문장 요약

주어진 9명의 키에서 7명을 골라 합이 100이 되는 경우를 찾고, 이를 오름차순으로 출력하는 문제이다.

📌 조건

• 입력: 9명의 키
• 출력: 합이 100이 되는 7명의 키를 오름차순으로 출력
• 조건: 9명 중 7명을 선택해야 함 (조합)

유형 분석

• 수가 많지 않음 → 모든 경우 탐색 가능 → 완전 탐색
• 7명을 선택해야 함 → 조합 사용 가능 → 총합에서 2명 제외 가능

---

2. 의사코드

1. 9명의 키를 입력받는다.
2. 9명의 키 총합을 구한다.
3. 9명 중 2명을 제외하여 합이 100이 되는 경우 찾기:
   • 완전 탐색: 이중 for문을 사용하여 9명 중 2명을 선택
   • 조합 사용: combinations(9명, 7)으로 7명의 조합을 찾기
4. 정답을 오름차순으로 정렬한 후 출력한다.

---

3. 코드

🏷️ 1) 이중 for문을 이용한 풀이

import sys
heights = [int(input()) for _ in range(9)]
total_height = sum(heights)

for i in range(9):  # 첫 번째 난쟁이 제외
    for j in range(i + 1, 9):  # 두 번째 난쟁이 제외
        if total_height - (heights[i] + heights[j]) == 100:
            result = [heights[k] for k in range(9) if k != i and k != j]  # 두 명을 제외한 리스트 생성
            result.sort()  # 오름차순 정렬
            for h in result:
                print(h)
            sys.exit()  # 정답을 찾으면 프로그램 종료

🏷️ 2) 조합(combinations)을 이용한 풀이

from itertools import combinations
heights = [int(input()) for _ in range(9)]
total_height = sum(heights)

for exclude in combinations(heights, 2):  # 2명 조합을 생성
    if total_height - sum(exclude) == 100:
        result = sorted([h for h in heights if h not in exclude])
        for h in result:
            print(h)
        break

---

4. 최적화 방법

• sys.exit() 사용: 정답을 찾으면 즉시 종료하여 불필요한 반복을 방지
• sys.stdin.read 사용 가능: 여러 줄 입력을 빠르게 받을 수 있음