백준 문제 중 2309번, 브루트포스, ‘일곱난쟁이’
백준 문제 중 2309번
https://www.acmicpc.net/problem/2309
문제
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.
입력
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
출력
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.
풀이
Try 1
문제의 조건의 여집합으로 최적화 해서 구하기
9명중 7명의 합이 100이 되야하는 조건이므로 나머지 2명을 빼서 100이 되는경우를 구하면 된다.
from typing import List
h = [None]*9
for i in range(9): h[i] = int(input())
s = sum(h)
for i in range(9):
for j in range(9):
# i,j가 같은경우는 제외
if j==i:
continue
# s-h[i]-h[j]가 100이 될때 같같 one two에 저장
elif s-(h[i]+h[j])==100:
one,two = h[i],h[j]
break
# 9명중 2명을 제외하고 오름차순으로 정렬
h.remove(one)
h.remove(two)
h.sort()
for i in h: print(i)
20
7
23
19
10
15
25
8
13
[7, 8, 10, 13, 19, 20, 23]
Try2
단순하게 7번의 반복을 통해 접근 (재귀함수 이용)
7번의 for문을 쓸 수도 있지만 코드의 간결함을 위해 재귀함수로 작성했다.
재귀함수가 6번째 7번째 호출될때의 동작의 중간을 살펴보자
…(6번째 재귀 호출 이후 7번째 호출시)
-
if의 조건문에서 find_7이 재귀호출된다.
-
for i in range(len(h)): 에서 i=0 이고 h[6]을 ans에 append 한다.
-
find_7([ h[7], h[8], h[9] ], [ h[1], h[2], … h[6] ], 7)
-
find_7([ h[7], h[8], h[9] ], [ h[0],h[1] …, h[5], h[6] ], 7) 이 falae를 반환하면 ans에서 h[6]가 pop되고 2번의 for문으로 돌아간다.
-
for i in range(len(h)):에서 i = 1 일때 h[7]을 ans에 append 한다.
-
find_7([ h[7], h[8], h[9] ], [ h[1], h[2], … h[5], h[7] ], 7)
-
find_7([ h[7], h[8], h[9] ], [ h[0],h[1] …, h[5], h[7] ], 7) 이 falae를 반환하면 ans에서 h[7]가 pop되고 2번의 for문으로 돌아간다.
-
for i in range(len(h)):에서 i = 2 일때 h[8]을 ans에 append 한다.
-
find_7([ h[7], h[8], h[9] ], [ h[1], h[2], … h[5], h[8] ], 7)
-
find_7([ h[7], h[8], h[9] ], [ h[0],h[1] …, h[5], h[8] ], 7) 이 falae를 반환하면 ans에서 h[8]가 pop되고 2번의 for문으로 돌아간다.
-
for i in range(len(h)):에서 i = 3 일때 h[9]을 ans에 append 한다.
-
find_7([ h[7], h[8], h[9] ], [ h[1], h[2], … h[5], h[9] ], 7)
-
find_7([ h[7], h[8], h[9] ], [ h[0],h[1] …, h[5], h[9] ], 7) 이 falae를 반환하면 ans에서 h[8]가 pop되고 2번의 for문으로 돌아간다.
-
for 문이 종료되고 6번째 재귀호출로 올라가 다시 for문을 반복하며 모든 조합의 경우를 돌아보게된다.
from typing import List
h = [None]*9
for i in range(9): h[i] = int(input())
ans = []
loop = 0
def find_7(h:List[int],ans:List[int],loop:int)->int:
if loop==7:
if sum(ans)==100:
return True
else:
return False
else:
#
for i in range(len(h)):
ans.append(h[i])
if find_7(h[i+1:],ans,loop+1):
return True
else:
ans.pop()
return False
find_7(h,ans,loop)
ans.sort()
for a in ans: print(a)
20
7
23
19
10
15
25
8
13
[20, 7, 23, 19, 10, 8, 13]
재귀함수를 구성할때 꽤나 머리가 아팠다. 차라리 for문을 7개 하는게 나을듯 하다.
배운점
브루트 포스 문제를 풀때 재귀함수가 양날의 검이 될수 있단걸 느꼈다.
Leave a comment