[완전탐색] 백준 2309번 일곱 난쟁이 with Python3

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

문제

 

내 풀이

import itertools

midget = []
for i in range(9):
    midget.append(int(input()))

midget.sort()

result = list(itertools.combinations(midget, 7))

for i in range(len(result)):
    a = list(result[i])
    if sum(a) == 100:
        a.sort()
        for i in range(len(a)):
            print(a[i])
        break

해설

itertools 이라는 python 내장 함수로 사기쳤다;;

 

사실 모든 경우의 수를 만들어내는게 제일 구현하기 어려운 단계인데 이걸 함수로 그냥 스킵 해버렷으니 이게 맞나 싶다. 

 

정답 풀이

s = []
for i in range(9):
    s.append(int(input()))
sum_s = sum(s)
one = 0
two = 0
for i in range(8):
    for j in range(i + 1, 9):
        if sum_s - (s[i] + s[j]) == 100:
            one = s[i]
            two = s[j]
s.remove(one)
s.remove(two)
s.sort()
for i in s:
    print(i)

출처:https://pacific-ocean.tistory.com/220

 

해석

대부분 9명중 7난쟁이의 키의 합이 100일 경우 전체 합에서 100을 뺸 값을 만들어내는 두 원소만 제거하면 된다는 사실에 집중해 완전탐색을 시행했다.

 

이런식으로 문제를 해체해서 좀더 쉬운 문제로 만드는 방법을 익혀야하는데; 

배울점이 많다.