[BOJ][⚪2][백준#06603] 로또

문제 출처

BAEKJOON Online Judge #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이 하나 주어진다. 

출력

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

예제

입력

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

출력

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

My Sol

def f(i, N, nums):
    if len(stack)==6:
        print(*stack)
        return

    for k in range(i, N):
        stack.append(nums[k])
        f(k+1, N, nums)
        stack.pop()

while True:
    all = input()
    if all=='0':
        break

    all = list(map(int, all.split()))
    k, *nums = all
    stack = []
    f(0, k, nums)
    print()

input()이 ‘0’인 경우에 실행을 종료해야 하므로, while True에 내부 조건문을 이용하여 처음에 입력 데이터에 대한 종료 여부를 판단하였다. 만약 입력이 0이 아니라면, 처음 수를 k로 하고 나머지는 nums 리스트로 담기 위해 packing을 이용하여 처리하였다.

함수 내부에서 사용할 stack을 빈 리스트로 정의하고, 함수를 시작한다. k개의 숫자가 있고, 그 수의 집합은 nums이므로, for문의 시작으로 사용할 i, k, nums를 모두 함수 내부에 parameter로 전달해준다.

함수 내부에서는 stack의 크기가 6이면 stack을 unpacking하여 출력하고, 종료하는 재귀함수를 사용한다. 전달된 i를 for문의 시작점으로 하는데 최초엔 i는 0으로 전달되어 nums의 0번째 수부터 stack에 추가한다.

이후 다음 재귀함수는 현재 k 이후의 수부터 추가하는 방식으로 i자리에 k+1을 넣어 다음 depth에서는 이전 depth의 k에서 1을 추가한 인덱스부터 nums를 조회해 stack에 추가하는 것이다.

재귀함수 호출 이후에는 stack을 pop하여 해당 depth에서의 역할을 다한 nums[k]를 보내고 다음 nums[k]를 stack에 추가하며 재귀를 이어나간다.

결과

맞았습니다!!