[Baekjoon] 6603_로또

Silver II

문제(출처: https://www.acmicpc.net/problem/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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

 

 

입력

 

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다. 

 

출력 

 

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.
각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

 

 

문제 풀이

- my solution

 

import sys
from itertools import combinations #조합

if __name__=='__main__':
    while True:
        a=list(sys.stdin.readline().split())
        if a[0]=='0': # 종료 조건
            break
        else: #k=a[0], s=a[1::]
            s=a[1::]
            arr=list(combinations(s,6))
            for i in arr:
                print(' '.join(i))
            print()

 

combinations를 사용하여 모든 방법을 출력하여 쉽게 해결할 수 있는 문제였다.

 

❓ 초기 코드에서 왜 출력 초과가 발생하였는가?

종료 조건이 올바르지 않았기 때문이다. 초기에 a==0으로 종료 조건을 구현하여 제대로 종료하지 못하였기 때문에

실행이 끝나지 않아 출력 초과가 발생한 것이었다. 종료 조건을 제대로 설정한 후 바로 통과할 수 있었다.

 

 

 

---

생각🤔

 

다들 이렇게 푸는가 궁금해서 찾아보니 combinations로 풀기도 하고 dfs를 사용하여 풀기도 하는 것을 볼 수 있었다.

다음에 실력 향상을 위해 dfs를 사용하여 문제를 해결하도록 시도해봐야겠다.

 

---