[Python] 백준 2309 : 일곱 난쟁이

 

 

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

2309번: 일곱 난쟁이

 

브루드 포스 기본문제인 일곱 난쟁이를 풀어보았다.

이 문제를 풀어보면서 브루드포스에 대한 내용도 인지하였고, dfs를 사용하여 풀이했다.

 

short_men = [int(input()) for _ in range(9)]
search_short_men = []

def dfs(depth, start):
    if depth == 7:
        if sum(search_short_men) == 100:
            for j in sorted(search_short_men):
                print(j)
            exit()
        else:
            return
    
    for i in range(start, len(short_men)):
        search_short_men.append(short_men[i])
        dfs(depth+1, i + 1)
        search_short_men.pop()

dfs(0, 0)

 

 

 

다른 풀이로는 combinations를 이용하여 풀이하였다.

import itertools

short_men = [int(input()) for _ in range(9)]
search_short_men = []

for i in itertools.combinations(short_men, 7):
    if sum(i) == 100:
        for j in sorted(i):
            print(j)
        break