[BOJ/python] 6603: 로또

문제

✔️ silver 2
수학
조합론
백트래킹
재귀

문제 흐름

갑자기 감 잃을까봐 푸는 다른 유형 (=백트래킹)문제~

1. while문을 통해 0이 들어올 때까지 입력을 받아준다.
2. 수열은 s에 리스트의 형태로 저장한다.
3. 백트래킹 함수 bt를 호출한다. (4~
4. lst는 경우의 수를 저장해 출력하는 용도의 리스트 (함수 외부에 선언),
   i는 현재까지 고른 숫자들의 수 (6개를 골랐다면 출력해야 함),
   cur는 현재 가장 최근에 선택한 숫자의 인덱스이다.
5. 함수 bt에 들어오면 0 부터 n-1까지의 idx에 대하여 idx가 cur보다 큰 경우 lst에 s의 해당 인덱스 원소를 append한 뒤 i를 1증가하여 다시 bt를 호출하여 반복한다.
6. 함수의 가장 앞에서 i가 6이면(6개의 숫자를 모두 고른 경우) 나머지 코드를 실행하지 않고 lst를 출력한 뒤 리턴한다.

코드

# 로또
# bt

import sys
input = sys.stdin.readline

lst = []

def bt (i: int, cur: int, s: list):
    if i == 6:
        print(*lst)
        return

    for idx in range(len(s)):
        if idx <= cur:
            continue
        lst.append(s[idx])
        bt(i + 1, idx, s)
        lst.pop()


if __name__ == "__main__":
    while 1:
        inp = list(map(int, input().split()))
        k = inp[0]
        if k == 0:
            break
        s = inp[1:]

        # print(f"s: {s}")
        bt(0, -1, s)
        print()