이 문제는 브루트 포스 문제이다.
문제에서 의도하는 바는 9명의 난쟁이 중 키의 합이 100이 되는 7명의 난쟁이를 고르는 것이다. (가능한 경우의 수가 여러 개일 경우 한 가지만 출력한다.)
이제 웬만한 브루트 포스 문제는 막힘없이 풀 수 있는 것 같아서 조금 성장한 느낌이 든다.
문제를 푼 로직은 다음과 같다.
- DFS를 재귀적으로 사용하여 각 난쟁이를 선택한 경우와 선택하지 않은 경우의 수를 모두 구한다. (19~25번째 줄)
- 모든 경우 중 한 가지 경우의 난쟁이들을 선택한 뒤, 선택한 난쟁이의 수가 7이고 키의 합이 100인 경우 선택된 난쟁이들의 키를 출력한다. (9~17번째 줄)
이 문제를 풀면서 한 가지 배운 점이 있다면, 한 개의 리스트를 출력할 때, 리스트의 원소마다 구분자를 설정하여 한 줄로 출력할 수 있다는 것이다.
이는 15번째 줄에 다음과 같이 나타나 있다.
print(*sorted(answer), sep='\n')
import sys
dwarf_list = [int(sys.stdin.readline()) for _ in range(9)]
dwarf_check = [0 for _ in range(9)]
answer = []
def dfs(n, count, sum_height):
if n == 9:
if count == 7 and sum_height == 100:
for idx, v in enumerate(dwarf_check):
if v:
answer.append(dwarf_list[idx])
print(*sorted(answer), sep='\n')
sys.exit(0)
return
# select a dwarf
dwarf_check[n] = 1
dfs(n + 1, count + 1, sum_height + dwarf_list[n])
# don't select a dwarf
dwarf_check[n] = 0
dfs(n + 1, count, sum_height)
dfs(0, 0, 0)
