[백준] 2309 일곱 난쟁이

문제 출처: 백준 온라인 저지

2309번: 일곱 난쟁이

 

문제 설명

🔎왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

리스트의 길이가 9로 고정된 비교적 간단한 브루트포스 문제였다. 7명의 키의 합이 100이 되는 경우 중 한가지만 출력하면 된다.

 

7명을 선택하는 방법은 $$ _{9}\mathrm{C}_{7} $$ 로 36가지만 검토하면 되므로 Combination(조합)을 이용해서 풀어도 시간 제약에 걸리지 않고 통과할 것이다.

 

코딩 테스트 도중이라면 위 방법이 먹힘을 확인하고 바로 넘어갔겠지만, 통과하지 못하는 시간 제약이 있을 수도 있어 stack을 이용한 풀이까지 해서 총 2가지 방법으로 풀어보았다.

 

<정답 코드1>

import sys
from itertools import combinations
inp = sys.stdin.readline

heights = []
for _ in range(9):
    heights.append(int(inp()))

heights.sort()

kinds = list(combinations(heights, 7))

for i in kinds:
    if sum(i) == 100:
        print(*i, sep='\n')
        break

 

우선은 조합을 이용한 풀이다.

itertools에서 제공하는 combinations를 활용해 가능한 모든 조합을 도출하고, 조합 안에서 합이 100인 리스트가 존재하면 출력하고 종료하는 것으로 매우 간단한 코드다.

 

<정답 코드2>

import sys
inp = sys.stdin.readline

heights = []
for _ in range(9):
    heights.append(int(inp()))

heights.sort()

for i in range(9):
    for j in range(i, 9):
        if sum(heights) - (heights[i]+heights[j]) == 100:
            heights.pop(j)
            heights.pop(i)
            print(*heights, sep='\n')
            exit()

반복문을 통해 조합을 구현하되, 7명이 아닌 2명을 선택하고, 최악의 경우는 모든 조합을 검토하지만 최선의 경우에는 한번만 점검해도 답이 도출된다는 점에서 combinations보다 빠를 것으로 기대된다.

 

접근방법은 아래와 같다.

 

1. 출력이 오름차순으로 되어야하므로 미리 정렬시켜놓는다.

2. 이중 반복문을 통해 2명을 선택할 수 있는 모든 경우의 수를 순회한다.

3. 순회 도중 합이 100임을 만족하는 선택지가 있으면 해당 2명을 pop한 후 프로그램을 종료한다.

 

문제만 차분히 읽는다면 충분히 빠른 시간 안에 해결할 수 있는 문제였다.