[백준] 2309번(일곱 난쟁이)

백준 2309번

최종 제출 코드

# 필요한 변수 선언
array = [0]*9
n = 7
ans = []

# 배열 입력 받기
for l in range(9):
  array[l] = int(input())

# k번째 원소를 배열에 추가
def append_element(arr, k):
  if k>len(array)-1:
    return
    
  _arr = arr[:]
  _arr.append(array[k])
  
  if len(_arr) < n:
    make_comb(_arr, k+1)
  else:
    ans.append(_arr)
    return

# k번째 원소를 배열에 추가하지 않고 그대로 배열을 넘김
def do_nothing(arr, k):
  if k>len(array)-1:
    return
    
  _arr = arr[:]
  make_comb(_arr, k+1)

# appendElement 함수와 doNothing 함수를 호출
def make_order(arr, k):
  append_element(arr, k)
  do_nothing(arr, k)

# 조합 생성 시작
make_comb([], 0)

# ans에 추가된 원소 중 합이 100인 배열의 원소를 오름차순으로 출력
for i in range(len(ans)):
  if sum(ans[i])==100:
    ans[i].sort()
    for j in range(n):
      print(ans[i][j])
    break

.
◼ 먼저 조합을 구하는 코드를 작성

• k번째 원소를 포함하는 배열을 생성하는 함수와 그렇지 않은 함수 작성
• k가 배열의 마지막 원소 인덱스보다 커지면 함수 종료
• append_element, do_nothing 함수의 마지막에 make_comb 함수 호출하여 각각의 경우를 k+1번째 원소에 대해서 또 다시 분기함
• 배열의 길이가 n의 값과 같을 경우 ans에 배열 삽입

.
◼ 합이 100이 되는 배열을 오름차순으로 출력