백준 2309번 파이썬 문제풀이(브루트 포스 - 일곱 난쟁이)

---

 

 

정답코드1 - for문 이용

---

array = []
for i in range(9):
    array.append(int(input()))

array.sort()

sum_ = sum(array)

# 만약 모두다 더하고 2명을 뺐을 때 그 값이 100이라면 2개를 뺀 나머지 값들 출력
for i in range(len(array)):
    for j in range(i + 1, len(array)):
        if sum_ - array[i] - array[j] == 100:
            for k in range(len(array)):
                if k == i or k == j:
                    pass
                else:
                    print(array[k])
            exit()

-> 이문제를 잘생각해보면 9명 중에 7명을 뽑아서 그 합이 100이면 그 7개의 값을 보여주면된다. 그런데 7개를 어떻게 뽑을 것이라는 거다. 반복문을 7개 중첩할 수 도 없는 노릇. 그렇다면 반대로 생각해볼 필요가 있다. 만약 9명중에 2명을 뽑아서 그 2명의 키를 뺀 값이 100이라면 반복문을 2번만 돌 수 있지 않을까라는 생각이다. 따라서 이러한 개념을 위의코드로 구현 했다.

 

정답코드2 - combinations 라이브러리 이용

---

import itertools

array = [int(input()) for _ in range(9)]

for i in itertools.combinations(array, 7):  # 해당 배열을 7명 중복없이 뽑아준다.
    if sum(i) == 100:  # 그합이 100이라면
        for j in sorted(i):  # 그 7명을 오름차순으로 정렬후 출력한다.
            print(j)
        break #그 후 반복문 탈출

-> 파이썬에서는 9명중에 7개를 뽑는 조합과 순열의 라이브러리를 제공한다. 순열은 from itertools import permutations , 조합은 from itertools import combinations 에 있는 라이브러리를 이용한다. 

정답코드3 - 재귀이용

---

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를 돈다.

-> 반복문을 7번 돌아야 하므로 재귀를 돌면 쉽게 풀 수 있다.

 

---

다음은 조합과 순열 구하는 라이브러리의 간단한 설명이다.

 

https://ourcstory.tistory.com/414

파이썬(Python) 리스트 모든 조합 구하기 (combination vs permutations vs product)