[python] 백준 6603번 : 로또 (combination, backtracking)

jmHan 2022. 2. 25. 18:57

https://www.acmicpc.net/problem/6603

6603번: 로또

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

www.acmicpc.net

1. combination 사용

from itertools import combinations

while True:
    s = list(map(int, input().split()))
    if len(s) == 1 and s == [0]:
        break
    k = s.pop(0)
    for data in list(combinations(s, 6)):
        print(*data)
    print()

2. 백트래킹 구현

def dfs(stack, idx):
    if len(stack) == 6:
        # print 한다
        print(*stack)
        return
    for idx in range(idx, k):
        # 원소를 추가한다
        stack.append(s[idx])
        dfs(stack, idx+1)
        stack.pop()


while True:
    s = list(map(int, input().split()))
    k = s.pop(0)
    if not s:
        break
    dfs([], 0)
    print()