[백준] 2309 - 일곱 난쟁이 (Python)

문제

https://www.acmicpc.net/problem/2309

문제 설명

일곱 난쟁이들의 키의 합이 100이라는 사실을 통해 입력받은 9명의 난쟁이들에서 정답이 아닌 2명을 제외한 7명의 키의 합이 100이 된다는 것으로 모든 경우의 수를 구하는 문제이다.

제출 코드

list = [int(input()) for i in range(9)]

total = sum(list)

for i in range(8):
    for j in range(i+1, 9):
        if 100 == total - (list[i] + list[j]):
            num1 = list[i]
            num2 = list[j]
            
list.remove(num1)
list.remove(num2)
list.sort()  

for i in range(len(list)):
    print(list[i])

결과

정리

개념

이 문제도 '1476 - 날짜 계산' 문제와 마찬가지로 브루트포스 알고리즘이다.

• 브루트포스 알고리즘: 완전탐색 알고리즘이다. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

sum(9명) - (난쟁이1 + 난쟁이2) == 100과 같은 말이다. 그런데 몇 번 난쟁이가 들어가야 할지 모르기 때문에 모든 경우의 수를 찾아야 한다.

주석있는 코드

#입력받기
list = [int(input()) for i in range(9)]

total = sum(list)

for i in range(8):
    for j in range(i+1, 9):
        if 100 == total - (list[i] + list[j]):
            num1 = list[i]
            num2 = list[j]

list.remove(num1)
list.remove(num2)
list.sort()  #오름차순 정리

#결과출력
for i in range(len(list)):
    print(list[i])

느낀점

모든 경우의 수를 확인해야 되서 for문을 많이 돌려야 되는데 그걸 효율적으로 하는게 어려웠던 것 같다.