[Python | 6603] 로또

https://www.acmicpc.net/problem/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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

 

📌 시간 제한: 2초

---

입력

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

입력의 마지막 줄에는 0이 하나 주어진다. 

---

출력

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

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

---

문제 접근

이 문제는 k개의 숫자 중에서 6개를 선택하는 모든 조합을 구하는 문제다.
즉, "순서를 고려하지 않고, 중복 없이 여러 개의 요소를 선택하는 문제"이다.

이런 문제를 해결하는 대표적인 접근 방식으로 완전 탐색(Brute Force), DFS(백트래킹), 동적 계획법(DP) 등이 있다.

완전 탐색 (Brute Force)

가장 단순한 방법은 모든 경우의 수를 나열하는 것이다.
즉, k개의 숫자에서 6개를 선택하는 모든 조합을 하나씩 만들어보는 방식이다.

하지만 이 방식은 연산량이 너무 많아 비효율적이다.

• k = 13일 경우, 가능한 조합의 개수는 C(13,6) = 1716개.
• 작은 입력에서는 가능하지만, k가 더 커지면 모든 경우를 나열하는 것은 연산량이 급증하여 비효율적이다.

동적 계획법 (DP)

DP는 부분 문제의 결과를 저장하여 중복 계산을 줄이는 방식이다.
하지만 이 문제는 중복된 부분 문제가 존재하지 않으며, 매번 다른 조합을 구해야 한다.

DP는 주로 최적해(Optimal Solution)를 찾는 문제에서 유용하지만,
이 문제는 단순히 모든 가능한 조합을 나열하는 문제이므로 DP를 적용하기 어렵다.

➡ DP는 조합을 "나열하는" 문제보다는 "최적의 조합"을 찾는 문제에 더 적합하다. 따라서 이 문제에는 적절하지 않다.

 

DFS + 백트래킹

이 문제는 모든 경우를 탐색해야 하지만, 불필요한 탐색을 줄이는 것이 핵심이다.
DFS(깊이 우선 탐색)를 활용하면 재귀적으로 조합을 생성하면서,
백트래킹을 통해 더 이상 탐색할 필요가 없는 경우 가지치기(Pruning)할 수 있다.

1. 재귀 호출을 이용해 조합을 쉽게 구성할 수 있다.
   • k개의 숫자 중에서 현재까지 선택한 숫자를 기록하면서 탐색이 가능하다.
2. 이미 선택한 숫자보다 작은 숫자는 다시 선택하지 않는다.
   • 조합의 특성상 [1, 2, 3]과 [3, 2, 1]은 동일한 조합이므로 중복을 방지할 필요가 있다.
   • i+1부터 탐색하도록 제한하면 중복된 조합이 생성되지 않는다.
3. 백트래킹을 사용하여 불필요한 연산을 줄인다.
   • 6개를 선택하면 즉시 탐색을 종료하여 추가적인 연산을 방지한다.

DFS(재귀)를 이용해 조합을 만들고, 백트래킹을 활용하여 불필요한 탐색을 줄이는 것이 가장 효율적인 방법이다.

---

구현

1️⃣ DFS를 통해 조합을 생성

• dfs(start, path)를 호출하면 start개까지 선택한 숫자에서 탐색을 시작한다.
• path는 선택할 수 있는 숫자의 시작 위치로, 이전보다 작은 숫자는 다시 선택하지 않는다.
• start == 6이면 6개의 숫자가 선택된 것이므로 출력하고 종료한다.

2️⃣ 백트래킹을 사용하여 중복된 조합을 방지

• 숫자를 선택한 후, 다른 조합을 찾기 위해 pop()을 사용한다.
• 이렇게 하면 이미 선택된 숫자를 다시 선택하지 않으면서, 모든 조합을 탐색할 수 있다.

def dfs(start, path):
    if start == 6:  # 6개를 선택한 경우 출력
        print(*out)
        return
    
    for i in range(path, k):  # 이전에 선택한 숫자 이후부터 탐색
        out.append(s[i])
        dfs(start + 1, i + 1)  # 다음 숫자를 선택할 때 현재 숫자보다 큰 것만 선택
        out.pop()  # 백트래킹

while True:
    data = list(map(int, input().split()))
    k = data[0]
    s = data[1:]

    out = []
    dfs(0, 0)	# DFS 탐색 시작
    if k == 0:
        exit()

    print()