문제풀이/백트래킹
[Python/파이썬] 백준 2309번 일곱 난쟁이
딜레이레이
2024. 3. 4. 12:59
2309번: 일곱 난쟁이
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
www.acmicpc.net
코드
백트래킹
h = [int(input()) for _ in range(9)]
def bt(idx, picked):
if len(picked) == 7:
if sum(picked) == 100:
print(*sorted(picked))
exit()
if idx >= 9:
return
if len(picked)+(9-idx) >= 7:
bt(idx+1, picked+[h[idx]])
bt(idx+1, picked)
bt(0, [])
재귀적으로 함수를 호출하여 7개를 뽑는 경우를 구한다. 이때 유망하지 않은 경우, 즉 뽑은 숫자들의 배열인 picked의 길이와 뽑을 수 있는 남은 숫자들의 개수를 합쳐도 7 이상이 되지 않는 경우에는 더이상 재귀호출을 하지 않는다.
itertools 라이브러리 이용
from itertools import combinations
h = [int(input()) for _ in range(9)]
for comb in combinations(h, 7):
if sum(comb) == 100:
print(*sorted(comb))
break
파이썬의 itertools 라이브러리의 combinations 함수는 조합을 구할 수 있기 때문에 이 함수를 이용해도 된다.