[백준] 6603, 로또 (파이썬)

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

6603번: 로또

 

문제 설명

🔎 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

출처: 백준 온라인 저지

---

<정답 코드>

from heapq import heapify, heappop
from itertools import combinations

while True:
    inp = list(map(int, input().split()))
    if inp == [0]:
        break

    n = inp[0]
    inp = inp[1:]
    com = list(combinations(inp, 6))
    heapify(com)

    while com:
        print(*heappop(com))

    print()

combinations를 통해 구현하는 간단한 문제였다.

 

접근은 아래와 같다.

1. 입력 받은 배열을 k와 S로 구분한 후, combinations를 이용해 6개를 뽑는 집합을 만든다.
2. 집합을 heapq를 통해 정렬한 후 heappop하면서 오름차순으로 뽑는다.

이 전에 비슷한 문제들을 풀었던 것과 달리 min heap을 활용해서 정렬해보았다.