[파이썬] 백준 2309 일곱 난쟁이 (조합 combination)

✅ 백준 문제 링크: 백준 2309번 - 일곱 난쟁이

백준 2309

1. 조합(Combination) 이란?

 

조합이란, 서로 다른 n개의 원소 중에서 r개를 중복 없이 선택하는 방법을 의미한다.

순서는 고려하지 않으며, 파이썬에서는 itertools.combinations() 함수를 사용하여 쉽게 구현할 수 있다.

 

📌 조합 예제

from itertools import combinations

people = ['A', 'B', 'C']
combi = list(combinations(people, 2))  # 3명 중에서 2명을 선택하는 경우의 수
print(combi)

 

🔹 출력:

[('A', 'B'), ('A', 'C'), ('B', 'C')]

 

2. 문제 설명

 

아홉 난쟁이 중에서 일곱 명을 골라 키의 합이 100이 되는 경우를 찾는 문제다.

• 입력: 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다.
• 출력: 조건을 만족하는 일곱 난쟁이의 키를 오름차순으로 출력한다.

✅ 가능한 정답이 여러 개일 경우, 아무거나 출력해도 된다.

 

3. 문제 해결 방법

1. 주어진 입력 값을 리스트에 담아 정렬해 놓는다.
2. 리스트의 값을 조합 함수 활용하여 7개의 요소로 조합된 리스트를 만든다.
3. 조합된 리스트로 반복하며 요소들의 합이 100 인 것을 출력한다.
4. 가능한 정답이 여러 가지인 경우에는 아무거나 출력하는 것이 조건이니, 정답을 찾으면 break로 빠져나간다.

4. 파이썬 코드 구현

from itertools import combinations
#1. 주어진 입력 값을 리스트에 담아 정렬해 놓는다.
k = [int(input()) for _ in range(9)]
k.sort()
#2. 리스트의 값을 조합 함수 활용하여 7개의 요소로 조합된 리스트를 만든다.
rst = list(combinations(k, 7))
i = 0
while i < len(rst):
    #3. 조합된 리스트로 반복하며 요소들의 합이 100 인 것을 출력한다.
    if sum(rst[i]) == 100:
        print(*rst[i], sep="\n")
        #4. 가능한 정답이 여러 가지인 경우에는 아무거나 출력하는 것이니 break 로 빠져나간다.
        break 
    i += 1

 

5. 예제 테스트

 

✔ 입력 예시

20
7
23
19
10
15
25
8
13

 

✔ 출력 예시

7
8
10
13
19
20
23

 

6. 시간 복잡도 분석

• 조합 연산: itertools.combinations(dwarfs, 7)의 경우의 수는 9C7 = 36가지이다.
• 각 조합의 합 계산: O(1), 최대 36번 반복
• 최대 연산 횟수: O(36), 충분히 빠름

✅ 조합을 활용하여 효율적으로 문제를 해결할 수 있다! 🚀