[ BOJ ] 2309 일곱난쟁이 - python 문제풀이

2309 일곱난쟁이

접근 : 특정 인덱스의 난쟁이 선택O/선택X으로 재귀, 총합 조건을 백트래킹에 활용

풀이 방법
- 미리 난쟁이 키 순서대로 정렬
- 인덱스를 1씩 올려가면서 해당 순서의 난쟁이 선택하거나 안하거나 2가지로 재귀
- 도중에 백트래킹으로 시간 초과 방지

 

def find(cnt,s,idx,li):
    global r
    if r != []: # 이미 결과 찾았으면 중단
        return
    if s > 100: # 100보다 커지는 순간 중단
        return
    if idx == 9: # 모든 난쟁이를 지나왔을 때,
        if cnt == 7 and s == 100: # 조건을 만족하는 조합이 있다면
            r = li # 결과로 지정하고 중단
        return
        
    # idx 번째 난쟁이를 선택하거나 선택하지 않는 경우를 재귀로...
    find(cnt,s,idx+1,li)
    find(cnt+1,s+h[idx],idx+1,li+[h[idx]])

h = list(int(input()) for _ in range(9))
h.sort()
r = []
find(0,0,0,[])
print("\n".join(map(str,r)))