[파이썬/Python] 백준 2309번: 일곱 난쟁이

📌 문제 : 백준 2309번

---

📌 문제 탐색하기

heights : 난쟁이들의 키를 저장한 리스트

height : 아홉 난쟁이 각각의 키

height의 조건

1. height ≤ 100
2. 각 height는 모두 다른 숫자
3. 구해야 할 일곱 난쟁이의 height 합은 100

9개의 height 중 랜덤으로 7개를 선택했을 때, 그 height들의 합이 100인 경우를 찾아야 한다.

입력받은 heights를 오름차순 정렬한 후, heights 중에서 원소의 개수가 7인 조합을 구하고, 그 조합의 합이 100인 경우를 if문으로 찾으면 될 것 같다.

조합은 itertools 라이브러리의 combinations를 이용한다.

가능한 시간복잡도

최대 9번 입력받게 되어 길이가 9인 리스트를 오름차순 정렬한다.
→ sort() 함수로 오름차순 정렬하므로 $O(NlogN)=O(9log9)$ 보장

9개 중 7개 조합을 구한다
→ $_{9}C_{2}=36$

이 문제의 시간복잡도는 $O(1)$을 가지게 될 것이다.

---

📌 코드 설계하기

1. for문으로 height 입력받아 heights에 추가
2. heights 정렬
3. 9개 중 7개를 선택하는 조합 계산
4. 원하는 형식으로 출력
   
   

---

📌 정답 코드

import sys
from itertools import combinations

input = sys.stdin.readline

# 1. for문으로 height 입력받아 heights에 추가
heights = [int(input().rstrip()) for _ in range(9)]

# 2. heights 정렬
heights.sort()

# 3. 9개 중 7개를 선택하는 조합 계산
for i in combinations(heights, 7):
    if sum(i) == 100:
        answer = i
        break

# 4. 원하는 형식으로 출력
for i in range(len(answer)):
    print(answer[i])
    

• 결과
  

추가 풀이

• 조합을 이용한 풀이가 생각나기 전, 9개 중 제거할 2가지를 골라서 나머지의 합을 구하는 방식을 생각했었다. 위의 정답 코드와 메모리, 시간 부분에서 얼마나 차이나는지 궁금해서 확인해보았다.
• 코드

  import sys
  
  input = sys.stdin.readline
  
  # 1. for문으로 height 입력받아 heights에 추가
  heights = [int(input().rstrip()) for _ in range(9)]
  
  # 2. heights 정렬
  heights.sort()
  
  # 3. 2가지 키를 제거하여 합이 100이 되는지 확인
  total_sum = sum(heights)
  found = False
  
  for i in range(8):
      for j in range(i + 1, 9):
          if total_sum - heights[i] - heights[j] == 100:
              answer = []
              
              for k in range(9):
                  if k != i and k != j:
                      answer.append(heights[k])
                      
              found = True
              break
      if found:
          break
  
  # 4. 원하는 형식으로 출력
  for height in answer:
      print(height)

• 결과
  • 9개 중 제거할 2개를 선택하는 가짓수가 더 적고, for문을 도는 횟수가 감소하기 때문에 훨씬 빠르게 연산된 것 같다.