arr = []
for _ in range(9):
f=int(input())
arr.append(f)
arr.sort()
sum_ = sum(arr)
fake=[]
# 7번 반복 대신 반대로 생각 9명 합에서 2명을 뺐을때 100 이하인 경우 찾기
for i in range(9):
for j in range(i+1,9):
if(len(fake)==2):
continue
if sum_-arr[i]-arr[j] ==100:
fake.append(arr[i])
fake.append(arr[j])
#list del method은 코테 풀이할때 가급적 쓰지 말자!
for i in arr:
if i in fake:
continue
print(i)
쉽게 생각하면 결국 9명 중 7명을 뽑아 그 합이 100이면 해당 원소값들을 출력해주면 된다. 그런데 이 7개를 어떻게 구현하여 뽑아야할까? 단순 반복문을 7개 중첩하는 것은 매우 비효율적이므로 반대로 생각을 해보자. 9명 중 2명을 뽑아 그 2명 키의 합을 전체 키에서 뺀 값이 100이라면 반복문을 7회->2회만 중첩하여 실행시키면 된다. 위 코드는 해당 개념을 구현한 것이다.
# combinations
def combinations(array, r):
for i in range(len(array)):
if r == 1:
yield [array[i]]
else:
for next in combinations(array[i+1:], r-1): # 현재 target 원소 이후만 인덱싱하여 배열 재구성
yield [array[i]] + next
for i in combinations(arr,7):
if sum(i) == 100: # 그합이 100이라면
for j in sorted(i): # 그 7명을 오름차순으로 정렬후 출력한다.
print(j)
break #그 후 반복문 탈출
itertools 라이브러리를 직접 써도 된다.
from itertools import combinations
for i in combination(arr,7):
if sum(i) == 100: # 그합이 100이라면
for j in sorted(i): # 그 7명을 오름차순으로 정렬후 출력한다.
print(j)
break #그 후 반복문 탈출
1번은 역으로 풀이를 한 것이라면, 3번은 정석적으로(?) 풀이를 한 것이라고 볼 수 있겠다. 언급했듯 7번 중첩 반복문을 돌리는 것은 무리가 있으므로 재귀방식을 활용한다.
short_men = [int(input()) for _ in range(9)]
seven_short_temp = [] # 7명을 뽑아 합을 조사할 새로운 리스트 선언
def dfs(depth, start):
if depth == 7: # 만약 7번 재귀를 돌았다면
if sum(seven_short_temp) == 100: # 현재 저장된 일곱난쟁이들의 합이 100이라면
for j in sorted(seven_short_temp): # 오름차순으로 정렬 후 출력
print(j)
exit() # 그 후 코드 종료
else: # 만약 7명을 뽑았는데 합이 100이 아니라면
return # 해당 재귀를 더이상 실행하지 않고 종료
for i in range(start, len(short_men)): # 시작인덱스와 9명의 난쟁이가 있으므로 9번을 돈다.
seven_short_temp.append(short_men[i]) # 난쟁이 한명을 추가한다.
dfs(depth + 1, i + 1) # dfs를 돈다(다음번 깊이는 +1로 해주고 인덱스는 중복되지 않게 하기위해서 다음 인덱스를 넣어준다.)
seven_short_temp.pop() # dfs를 돌다 7명이 다 찼으나 합이 100이 아니어서 return 되었으면 넣었던 난쟁이 한명을 다시 빼준다.
dfs(0, 0) # dfs를 돈다.
코드의 이해를 돕기 위해 내부 반복 구조를 그려보았다.
많은 도움이 되었습니다, 감사합니다.