로또

문제

독일 로또는 {1, 2, ... , 49}에서 수 6개를 고릅니다. 로또 번호 선택시에 사용되는 가장 유명한 전략은 49가지 수중에 K개를 뽑은 집합 S에 대해서 수 6개를 고르는 전략입니다.
집합 S와 K가 주어졌을때, 수를 고르는 모든 방법을 구하는 문제입니다.

제약조건

• 6 < K < 13
• S의 원소는 오름차순
• 마지막줄에는 0이 주어집니다.

풀이

두가지 방법이 존재합니다.

1. combinations사용. 집합 S에서 6개를 뽑는 족족 출력합니다.
2. 재귀로 직접 combination을 구현합니다.

combination을 구현하게 되면 주의해야할점이 있습니다.
6개를 골랐는지 판단하기전에 선택에 대한 판단을 하면 안됩니다. idx가 범위를 넘어섰다는것은 더 이상의 가지뻗기가 불가능하다라는뜻이지 해당 상태가 정답이 아니라는것은 아닙니다.

예를 들어 6개중 4개를 뽑는 문제에서

위 사진과 같은 시점에서 판단을 내릴때 더 이상의 재귀가 불가능하다고 해서 정답이 아닌것은 아닙니다. 따라서 정답인지(4개를 뽑았는지) 아닌지의 판단이 우선되어야한다. 정답에 도달하면 끝이 나야합니다.

다음과 같은 로직입니다.
1. 정답인지?
2. 정답이면 반환(더 이상의 재귀가 필요없음.) 아니라면 재귀 또는 종료를 해야한다.
3. 재귀가 가능한가?
4. 재귀가 가능하면 재귀, 아니라면 종료한다.
5. 재귀

코드

'''
Created by jun on 21/05/20
'''
#itertools사용
from itertools import combinations

while True:
    N, *german_lotto = list(map(int,input().split()))
    if N == 0:
        break
    for case in combinations(german_lotto, 6):
        print(*case)
    print()

#combination 구현

#idx를 뽑아 case인 경우(길이가 6인경우) 출력한다.
def print_case(idx:int, case:list, german_lotto:list):
	#지금껏고른 집합의 크기가 6 ?
    if len(case) == 6:
    	#정답이다.
        print(*case)
        return
    
    #해당 idx가 선택이 가능한지?
    if idx == len(german_lotto):
    	#선택 불가능/ 끝에 도달했다 / 정답이 아니다.
        return
        
	#해당 idx가 선택 가능하다.
    #선택한다.
    print_case(idx+1, case+[german_lotto[idx]], german_lotto)
    #선택하지 않는다.
    print_case(idx+1, case, german_lotto)


while True:
    N, *german_lotto = list(map(int,input().split()))
    if N == 0:
        break

    print_case(1, [german_lotto[0]], german_lotto)
    print_case(1, [], german_lotto)
    print()

새로 알게된 사실