[PS] BOJ 6603 / 로또

Minjun Kim

21 Nov 2025 • 1 min read

Thumbnail: Photo by dylan nolte (Unsplash)

문제 링크: https://www.acmicpc.net/problem/6603

백트래킹의 기본적인 구조만 이해한다면 쉽게 풀 수 있습니다.

풀이

$K$개의 원소를 가지는 집합 $S$에서, 6개의 숫자를 오름차순으로 고르는 모든 경우를 출력하는 문제입니다. ($6 < K < 13$으로 크지 않습니다.)

입력에서 집합 $S$의 원소는 항상 오름차순으로 주어지기 때문에, 항상 이전에 고른 수보다 뒤에 위치한 수들을 고르는 방식으로 6개의 수를 고른다면 사전 순으로 결과를 출력할 수 있습니다.

전체 코드

input = open(0).readline

S = [] # 숫자를 고를 집합
K = 0 # 집합 S의 원소의 개수
used = [False] * 12 # 6 < k < 13
selected = [0] * 6 # 독일 로또는 6개의 숫자로 구성됨

def select_numbers(depth, prev_num_idx):
    global K
    if depth == 6:
        print(*selected)
        return
    
    for i in range(prev_num_idx + 1, K):
        if not used[i]:
            selected[depth] = S[i]
            used[i] = True
            select_numbers(depth + 1, i)
            used[i] = False
    selected[depth] = 0

while True:
    line = input().rstrip()
    if line[0] == "0":
        break

    K, *S = map(int, line.split())
    for i in range(K):
        if i < 6:
            selected[i] = 0
        used[i] = False
    select_numbers(0, -1)
    print()

solution.py