백준 온라인 저지, DFS / 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이 하나 주어진다. 

출력

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

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

제한

예제 입력 1

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력 1

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

힌트

W3sicHJvYmxlbV9pZCI6IjY2MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWI2MTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNjNVx1Yzc3YyBcdWI4NWNcdWI2MTBcdWIyOTQgezEsIDIsIC4uLiwgNDl9XHVjNWQwXHVjMTFjIFx1YzIxOCZuYnNwOzZcdWFjMWNcdWI5N2MgXHVhY2UwXHViOTc4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI4NWNcdWI2MTAgXHViYzg4XHVkNjM4XHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWMwYWNcdWM2YTlcdWI0MThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWM4MDRcdWI3YjVcdWM3NDAgNDlcdWFjMDBcdWM5YzAgXHVjMjE4IFx1YzkxMSBrKGsmZ3Q7NilcdWFjMWNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWNlOFx1Yjc3YyBcdWM5ZDFcdWQ1NjkgU1x1Yjk3YyBcdWI5Y2NcdWI0ZTAgXHViMmU0XHVjNzRjIFx1YWRmOCBcdWMyMThcdWI5Y2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBrPTgsIFM9ezEsMiwzLDUsOCwxMywyMSwzNH1cdWM3NzggXHVhY2JkXHVjNmIwIFx1Yzc3NCBcdWM5ZDFcdWQ1NjkgU1x1YzVkMFx1YzExYyBcdWMyMThcdWI5N2MgXHVhY2UwXHViOTdjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWNkMWQgMjhcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIChbMSwyLDMsNSw4LDEzXSwgWzEsMiwzLDUsOCwyMV0sIFsxLDIsMyw1LDgsMzRdLCBbMSwyLDMsNSwxMywyMV0sIC4uLiwgWzMsNSw4LDEzLDIxLDM0XSk8XC9wPlxyXG5cclxuPHA+XHVjOWQxXHVkNTY5IFNcdWM2NDAga1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWMyMThcdWI5N2MgXHVhY2UwXHViOTc0XHViMjk0IFx1YmFhOFx1YjRlMCBcdWJjMjlcdWJjOTVcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMThcdWIyOTQgayAoNiAmbHQ7IGsgJmx0OyAxMylcdWM3NzRcdWFjZTAsIFx1YjJlNFx1Yzc0YyBrXHVhYzFjIFx1YzIxOFx1YjI5NCBcdWM5ZDFcdWQ1NjkgU1x1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjMjE4XHVjNzc0XHViMmU0LiBTXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjI5NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjMjE4XHViOTdjIFx1YWNlMFx1Yjk3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVkNTU4XHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI2NjAzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTG90dG8iLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSBHZXJtYW4gTG90dG8geW91IGhhdmUgdG8gc2VsZWN0IDYgbnVtYmVycyBmcm9tIHRoZSBzZXQgezEsMiwuLi4sNDl9LiBBIHBvcHVsYXIgc3RyYXRlZ3kgdG8gcGxheSBMb3R0byAtIGFsdGhvdWdoIGl0IGRvZXNuJiMzOTt0IGluY3JlYXNlIHlvdXIgY2hhbmNlIG9mIHdpbm5pbmcgLSBpcyB0byBzZWxlY3QgYSBzdWJzZXQgUyBjb250YWluaW5nIGsgKGsmZ3Q7Nikgb2YgdGhlc2UgNDkgbnVtYmVycywgYW5kIHRoZW4gcGxheSBzZXZlcmFsIGdhbWVzIHdpdGggY2hvb3NpbmcgbnVtYmVycyBvbmx5IGZyb20gUy4gRm9yIGV4YW1wbGUsIGZvciBrPTggYW5kIFMgPSB7MSwyLDMsNSw4LDEzLDIxLDM0fSB0aGVyZSBhcmUgMjggcG9zc2libGUgZ2FtZXM6IFsxLDIsMyw1LDgsMTNdLCBbMSwyLDMsNSw4LDIxXSwgWzEsMiwzLDUsOCwzNF0sIFsxLDIsMyw1LDEzLDIxXSwgLi4uIFszLDUsOCwxMywyMSwzNF0uPFwvcD5cclxuXHJcbjxwPllvdXIgam9iIGlzIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IHJlYWRzIGluIHRoZSBudW1iZXIgayBhbmQgdGhlIHNldCBTIGFuZCB0aGVuIHByaW50cyBhbGwgcG9zc2libGUgZ2FtZXMgY2hvb3NpbmcgbnVtYmVycyBvbmx5IGZyb20gUy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBmaWxlIHdpbGwgY29udGFpbiBvbmUgb3IgbW9yZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBvbmUgbGluZSBjb250YWluaW5nIHNldmVyYWwgaW50ZWdlcnMgc2VwYXJhdGVkIGZyb20gZWFjaCBvdGhlciBieSBzcGFjZXMuIFRoZSBmaXJzdCBpbnRlZ2VyIG9uIHRoZSBsaW5lIHdpbGwgYmUgdGhlIG51bWJlciBrICg2ICZsdDsgayAmbHQ7IDEzKS4gVGhlbiBrIGludGVnZXJzLCBzcGVjaWZ5aW5nIHRoZSBzZXQgUywgd2lsbCBmb2xsb3cgaW4gYXNjZW5kaW5nIG9yZGVyLiBJbnB1dCB3aWxsIGJlIHRlcm1pbmF0ZWQgYnkgYSB2YWx1ZSBvZiB6ZXJvICgwKSBmb3Igay48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBhbGwgcG9zc2libGUgZ2FtZXMsIGVhY2ggZ2FtZSBvbiBvbmUgbGluZS4gVGhlIG51bWJlcnMgb2YgZWFjaCBnYW1lIGhhdmUgdG8gYmUgc29ydGVkIGluIGFzY2VuZGluZyBvcmRlciBhbmQgc2VwYXJhdGVkIGZyb20gZWFjaCBvdGhlciBieSBleGFjdGx5IG9uZSBzcGFjZS4gVGhlIGdhbWVzIHRoZW1zZWx2ZXMgaGF2ZSB0byBiZSBzb3J0ZWQgbGV4aWNvZ3JhcGhpY2FsbHksIHRoYXQgbWVhbnMgc29ydGVkIGJ5IHRoZSBsb3dlc3QgbnVtYmVyIGZpcnN0LCB0aGVuIGJ5IHRoZSBzZWNvbmQgbG93ZXN0IGFuZCBzbyBvbiwgYXMgZGVtb25zdHJhdGVkIGluIHRoZSBzYW1wbGUgb3V0cHV0IGJlbG93LiBUaGUgdGVzdCBjYXNlcyBoYXZlIHRvIGJlIHNlcGFyYXRlZCBmcm9tIGVhY2ggb3RoZXIgYnkgZXhhY3RseSBvbmUgYmxhbmsgbGluZS4gRG8gbm90IHB1dCBhIGJsYW5rIGxpbmUgYWZ0ZXIgdGhlIGxhc3QgdGVzdCBjYXNlLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

접근 방법

- DFS를 통해 최대 6개의 숫자를 뽑아 이를 출력한다.

코드

# https://www.acmicpc.net/problem/6603
# 접근 방법
# DFS를 통해 최대 6개의 숫자를 뽑아 이를 출력한다.
def dfs(caseOfLotto, idx):
    if len(caseOfLotto) == 6:
        for l in caseOfLotto:
            print(l, end = ' ')
        print()
        return
        
    for i in range(idx, len(lotto)):
        dfs(caseOfLotto + [lotto[i]], i+1)


while True:
    arr = list(map(int, input().split()))
    if arr[0] == 0:
        break
    lotto = arr[1:]
    dfs([], 0)
    print()