백트래킹 예제1 [ 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 번째 난쟁이를 선택하거나 선택하지 않는 경우를 재귀로..... 2021. 7. 19. 이전 1 다음
