[백준 2309번] 일곱 난쟁이

from itertools import combinations

array = [0]*9

for i in range(9):
  array[i] = int(input())

remain = sum(array)-100

com_list = list(combinations(array,2))

for i in com_list:
  if sum(i) == remain:
    array.remove(i[0])
    array.remove(i[1])
    break

array.sort()

for i in array:
  print(i)

이번 문제는 정렬보다는 9명의 난쟁이 중 키의 합이 100이 되도록 만드는 조건을 구현하는 것이 관건인 문제였다.

 

문제에서 일곱 난쟁이를 찾을 수 없는 경우는 없다는 조건이 주어졌기 때문에, 무조건 난쟁이 7명이상은 100을 넘긴다는 가정을 가지고 풀었다.

 

따라서 난쟁이 7명(100) + 난쟁이 2명(remain)에서, 조합(Combinations)를 사용해 난쟁이 9명 중 2명을 뽑았고 이 2명을 찾은 뒤 난쟁이 리스트에서 제외시켰다.

 

정렬과 수학적인 사고를 동시에 할 수 있고, 순열과 조합 라이브러리 itertools를 복습할 수 있는 좋은 문제였다 :)