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

✅문제

출처 : 백준

✅문제풀이

9명 중에서 난쟁이를 고르는 문제이기 때문에 조합문제이다.

9명 중에서 7명을 고르는 것과 9명 중에서 2명을 고르는 것은 같기 때문에 총합에서 2명의 난쟁이를 빼면 된다.

 

브루트포스로 문제를 풀 경우 

나머지 2명을 고르는 경우 : 9*9나머지 난쟁이의 키의 합을 고르는 경우 : 9총 : 9*9*9

O(N^3)

✅Code

import sys
#sys.stdin = open('D:/test.txt', 'r')

n=9
a=[int(input()) for _ in range(n)]
a.sort()
total = sum(a)

for i in range(0,n):
    for j in range(i+1,n):
        if total - a[i] - a[j] == 100:
            for k in range(0,n):
                if i==k or j ==k:
                    continue
                print(a[k])
            sys.exit(0)