Python으로 푸는 백준 2309. 일곱 난쟁이

백준 2309. 일곱 난쟁이

백설공주와 일곱난쟁이가 함께 살고 있었다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉명이 돌아왔다.

일곱 난쟁이의 키의 총 합은 100이다. 진짜 난쟁이를 골라내어 오름차순으로 키를 출력하는 프로그램을 짜시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

Github에서 코드 보기

문제 조건

입곱 난쟁이들의 키는 서로 달라야 한다.

입곱 난쟁이의 키는 100을 넘지 않는다.

일곱 난쟁이의 키를 오름차순으로 출력해야 한다.

일곱 난쟁이를 찾을 수 없는 경우는 없으며, 여러 가지 경우가 가능하다면 하나의 경우의 수만 출력한다.

문제 풀이

나는 itertools의 combinations(조합)으로 문제를 풀었다. 입력되는 난쟁이의 키는 9가지이고, 그 가운데 7가지를 골라내는 것이므로 itertools를 사용하더라도 시간 초과가 나지 않는다. 합이 100이면 조건에 해당하는 일곱 난쟁이이므로 출력해준다.

다른 사람의 코드를 보니 더 좋은 코드가 있어서 아래에 추가해두도록 하였다. 9가지 키 중에서 어차피 2개를 제외하는 것이므로 2중 for문을 사용하여 경우의 수를 제외해주는 방법이다. 따로 라이브러리를 사용하지 않더라도 문제를 풀 수 있기 때문에 기록해두고 싶다.

파이썬 코드 - itertools.combinations 사용 

import sys
from itertools import combinations
input = sys.stdin.readline
 
def solve(case):
    if sum(case) == 100:
        case = list(case)
        case.sort()
        for old in case:
            print(int(old))
        return True
    return False
 
if __name__ == "__main__":
    child = set()
    for i in range(9):
        nai = int(input().strip())
        if nai <= 100:
            child.add(nai)
 
    for case in combinations(child, 7):
        if solve(case):
            break
 

a=[]
for i in range(9):
    a.append(int(input()))
res=sum(a)
a.sort()
for i in range(9):
    for j in range(i+1,9):
        if res-a[i]-a[j]==100:
            for k in range(9):
                if k==i or k==j:continue
                else:
                    print(a[k])
            exit()