[파이썬] 백준 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로 빠져나간다.

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
"""

 

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

https://docs.python.org/ko/3/library/itertools.html#itertools.combinations

itertools — Functions creating iterators for efficient looping