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

백준 2309 일곱 난쟁이 문제 풀이

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

백준 2309

조합이란

서로 다른 n개의 원소에서 (단, 0<𝑟≤𝑛0<r≤n) 개를 중복 없이, 순서를 고려하지 않고 선택하는 것,

혹은 그 결과를 조합(combination)이라고 한다.

 

▶ 예시

A, B, C 가 있을 때 2명으로 선택되는 가짓수는 얼마나 될까?

(A, B), (A, C), (B, C) 로 총 3가지이고 이를 조합(combination)이라 한다.

 

여기서 중복을 허용하는 것은 순열(permutations)이다. 순열인 경우 총 6가지 가짓수가 나온다.

('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')

 

☞ 출처

조합

 

파이썬에서 조합은 itertools 모듈의 combinations 함수를 사용할 수 있다.

• itertools.combinations(iterable, r)

풀이

해당 문제는 파이썬(python)의 조합 함수를 활용해서 코딩할 수 있다.

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

"""
입력
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 
주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 
가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.
"""
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
"""
입력값
20
7
23
19
10
15
25
8
13

출력값
7
8
10
13
19
20
23
"""

 

☞ 파이썬 자습서 참고 사이트

itertools — Functions creating iterators for efficient looping