[백준 6603] 로또

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

---

[입력]

 

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

입력의 마지막 줄에는 0이 하나 주어진다. 

---

[출력]

 

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

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

---

[코드 전개 및 생각]

 

재귀적으로 코드를 작성할 때는 탈출 조건을 문제에서 찾아내는 것이 중요하다.

 

'로또 번호의 개수가 6개'는 재귀 함수의 탈출 조건으로,

'오름차순 형태의 번호 구성' 은 다음 수를 가져오는 백트래킹 조건으로 사용하였다.

 

입력받은 숫자들의 조합을 통해서 문제를 해결할 수 있지만, 백트래킹 카테고리에서 처음으로 등장하는 문제인 만큼 백트래킹을 사용하여 문제를 해결하고 싶었다.

 

아직 재귀적으로 코드를 짜는 게 미숙하여 많은 문제를 접해보는 것이 중요할 것 같다.

 

import sys
sys.setrecursionlimit(10000)

def backtracking(li, idx):
    if idx==6:
        print(' '.join(map(str, li)))
    else:
        for i in range(len(numbers)):
            if not li:
                backtracking(li+[numbers[i]], idx+1)
            else:
                if numbers[i]>li[-1]:
                    backtracking(li+[numbers[i]], idx+1)

while True:
    numbers = list(map(int, sys.stdin.readline().split()))
    N = numbers.pop(0)
    if N==0:
        break
    numbers.sort()

    backtracking([],0)
    print()