문제 링크

이 문제는 완전탐색, 조합의 개념을 이해하고 풀이할 수 있는 문제로 파악했다.

1. 조합되는 경우의 수를 itertools의 combination으로부터 구하고
2. 각 조합의 수의 총합이 100이 되면 출력하면 된다. (답이 여러 가지면 아무거나 출력해도 됨)

combination과 permutations의 반환값은 튜플임.

나의 풀이

from itertools import combination

v = []
result = []

for i in range(0, 9):
  v.append(int(input()))

for i in combination(v, 7):
  if(sum(i) == 100):
    result = i
    break

result = list(result)
result.sort()

for i in result:
  print(i)

해설을 보고 깨달음

• 튜플은 정렬이 안 되는 줄 알고 list로 변환하는 코드를 작성했는데 그럴 필요없이 sorted()를 사용하면 됨.

강사님 풀이

from itertools import combinations

heights = [int(input()) for _ in range(9)]
for combi in combinations(heights, 7):
  if sum(combi) == 100:
    for height in sorted(combi):
      print(height)

이 코드는 테스트케이스는 통과하지만 제출 시, 틀렸다고 한다. 그 이유는 100이 되는 값을 만족하는 수가 여러가지가 될 때, 위 코드에 반례가 생기기 때문이다.

내가 작성한 코드에서는 만족하는 숫자를 찾고 바로 break를 실행하여 조합에서 가장 먼저 찾은 숫자가 제출되도록 하였다.

그런데 강사님의 풀이 예시에서는 이에 대한 예외처리가 안 된다.

다음과 같이 break 문을 작성하면 정상 작동한다.

from itertools import combinations

heights = [int(input()) for _ in range(9)]
for combi in combinations(heights, 7):
  if sum(combi) == 100:
    for height in sorted(combi):
      print(height)
    break

다른 풀이

combinations를 사용하지 않고 푸는 법

• 9개 중에 7개를 뽑는 것 = 9개 중 2개를 뽑는 것과 같다. = 이중 for 문으로 풀이가능
• 전체 난쟁이 키를 더한 값을 저장하고, 이중 for문을 돌려 선정한 조합의 합을 빼줬을 때 100을 만족하면 된다.

heights = [int(input()) for _ in range(9)]
heights.sort()
tot = sum(heights)

def f():
  for i in range(8):
    for j in range(i+1, 9):
      if tot - heights[i] - heights[j] == 100:
        for k in range(9):
          if i != k and j != k:
            print(heights[k])
        return

f()

점검 포인트

1. 무식하게 모든 경우의 수를 다 살피더라도 시간 초과가 되지 않을지 확인
2. 될 것 같으면 완전탐색으로 풀이한다.

일단 완전 탐색으로 작성해보고, 안 될 것 같으면 다른 알고리즘을 생각해보자