문제
접근
완전 탐색 문제이다.
문제의 조건을 만족하는 경우를 직접 구해서 출력해야 한다.
보통 이런 문제를 풀 때 정답 배열을 만들고 넣었다 뺏다 하는 식으로 풀었었는데,
오늘은 조금 다르게 풀어봤다.
7명의 키를 더했을 때 문제의 조건인 키의 합이 100이면 True를 반환하고 아닌 경우 False를 반환하게 했다.
True가 반환되면 재귀를 종료하고 현재 난쟁이의 키를 배열에 담고 True를 반환한다.
이렇게 연쇄적으로 재귀가 종료되며 최종적으로 True를 달성했을 때 더했었던 난쟁이들을 배열에 모두 담아 반환하게 된다.
False인 경우는 for문을 마저 돌면서 만족하는 답을 찾아간다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def brute_force(arr, num, cnt, heightSum, ans):
if cnt == 7:
if heightSum == 100:
return True
else:
return False
for i in range(num, 9):
if brute_force(arr, i+1, cnt+1, heightSum + arr[i], ans):
ans.append(arr[i])
return True
return False
if __name__ == "__main__":
ans = []
arr = [int(input()) for _ in range(9)]
brute_force(arr, 0, 0, 0, ans)
ans = sorted(ans)
for item in ans:
print(item)