[백준] 2309번 일곱난쟁이

 

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

2309번: 일곱 난쟁이

 

풀이

입력으로 받는 9개의 숫자 중 7개의 합이 100이 되게 구해야한다.
이 경우에는 조합을 사용하여 9개 중 7개를 추출하여 모든 조합에 대하여 계산하면 쉽게 구할 수 있다.

9C7은 36으로 모두 확인한다고해도 많은 시간이 소요되지 않는다.

import itertools

data = []

for i in range(9):
    data.append(int(input()))

data.sort()


data_com = list(itertools.combinations(data, 7))

itertools의 combination 함수를 시용하여 조합을 쉽게 만들 수 있다.

 

for i in data_com:
    if sum(i) == 100:
        for j in i:
            print(j)
        break

이후 모든 조합에 대하여 합이 100이 되는지 계산하고 정답은 아무거나 출력하면 되기 때문에
답이 나오는 순간 출력 후 break를 해서 멈췄다.

 

전체 코드

import itertools

data = []

for i in range(9):
    data.append(int(input()))

data.sort()


data_com = list(itertools.combinations(data, 7))

for i in data_com:
    if sum(i) == 100:
        for j in i:
            print(j)
        break

순열, 조합을 구현할 수 있으면 쉽게 풀 수 있는 문제였다.