백준 no.3040/백설공주와 일곱 난쟁이/python
문제
매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다.
어느 날 광산에서 아홉 난쟁이가 돌아왔다. (왜 그리고 어떻게 아홉 난쟁이가 돌아왔는지는 아무도 모른다) 아홉 난쟁이는 각각 자신이 백설공주의 일곱 난쟁이라고 우기고 있다.
백설공주는 이런 일이 생길 것을 대비해서, 난쟁이가 쓰고 다니는 모자에 100보다 작은 양의 정수를 적어 놓았다. 사실 백설 공주는 공주가 되기 전에 매우 유명한 수학자였다. 따라서, 일곱 난쟁이의 모자에 쓰여 있는 숫자의 합이 100이 되도록 적어 놓았다.
아홉 난쟁이의 모자에 쓰여 있는 수가 주어졌을 때, 일곱 난쟁이를 찾는 프로그램을 작성하시오. (아홉 개의 수 중 합이 100이 되는 일곱 개의 수를 찾으시오)
입력
총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다.
[예제 입력]
1
2
3
4
5
6
7
8
9
7
8
10
13
15
19
20
23
25
출력
일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다.
[예제 출력]
1
2
3
4
5
6
7
7
8
10
13
19
20
23
풀이
[핵심 아이디어]
- 더했을 때 합이 100이 되는 조합을 찾기 위해서는 숫자들의 여러 조합들을 ‘일일이’ 따져봐야 함
[풀이 코드]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
import random
heights=[int(sys.stdin.readline()) for _ in range(9)]
stack= []
while True:
num = random.randint(0,8)
stack.append(num)
if len(set(stack))<7:
continue
elif len(set(stack))==7:
stack=[heights[i] for i in set(stack)]
if sum(stack)==100:
break
else:
stack = []
print(*sorted(stack))
- random 모듈을 사용하여 모든 조합을 만들고자 함
- 하지만, 이 방법은 시간 복잡도 문제가 걸림
[다른 풀이]
1
2
3
4
5
6
7
8
9
10
11
12
13
num = [int(input()) for _ in range(9)]
numSum = sum(num)
for faker1 in range(8):
for faker2 in range(faker1 + 1, 9):
if numSum - num[faker1] - num[faker2] == 100:
f1, f2 = num[faker1], num[faker2]
num.remove(f1)
num.remove(f2)
for t in sorted(num):
print(t)
break
if len(num) == 7:
break
- for문 2개 사용해서 여러 숫자의 조합을 봄
- 나머지 2개의 숫자를 숫자들의 합에서 뺏을때 100이라면, 해당 숫자 2개를 제거
📌things that you can get from this problem
브루트포스 알고리즘: 해가 존재할 것으로 예상되는 모든 영역 전체를 탐색하는 방법
- 무식하게 모든 경우의 수를 탐색하면서 요구조건에 충족하는 결과를 찾는 것
- 시간이 오래 걸릴지라도 정답은 100% 찾는다는 장점
- 탐색 방법: 순차 탐색(선형 구조), 깊이 우선 탐색(비선형 구조), 너비 우선 탐색(비선형)
- 트리 구조 탐색 방법을 연상하면 좀 더 쉬워짐
- ex) 10의 약수 합 찾기 etc.