[백준 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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

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

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

출력

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

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

입출력 예

입력	출력
7 1 2 3 4 5 6 7	1 2 3 4 5 6
8 1 2 3 5 8 13 21 34	1 2 3 4 5 7
0	1 2 3 4 6 7
	1 2 3 5 6 7
	1 2 4 5 6 7
	1 3 4 5 6 7
	2 3 4 5 6 7
	1 2 3 5 8 13
	1 2 3 5 8 21
	1 2 3 5 8 34
	1 2 3 5 13 21
	1 2 3 5 13 34
	1 2 3 5 21 34
	1 2 3 8 13 21
	1 2 3 8 13 34
	1 2 3 8 21 34
	1 2 3 13 21 34
	1 2 5 8 13 21
	1 2 5 8 13 34
	1 2 5 8 21 34
	1 2 5 13 21 34
	1 2 8 13 21 34
	1 3 5 8 13 21
	1 3 5 8 13 34
	1 3 5 8 21 34
	1 3 5 13 21 34
	1 3 8 13 21 34
	1 5 8 13 21 34
	2 3 5 8 13 21
	2 3 5 8 13 34
	2 3 5 8 21 34
	2 3 5 13 21 34
	2 3 8 13 21 34
	2 5 8 13 21 34
	3 5 8 13 21 34

풀이

이 문제는 파이썬의 내장함수(조합)로도 풀 수도 있는 문제지만 나는 백트래킹을 연습하고 있어서 백트래킹으로 풀었다.

먼저 백트래킹에 대해 알아야하는데 백트래킹은 "해를 구하는 도중에 해가 아니어서 막히면, 막히기 전으로 돌아가서 해를 찾는 방법"이라고는 나오는데 사실 무슨 말인지 모르겠어서 예시 문제를 보면서 이해했던 것 같다. 두 문제밖에 안 풀어봤지만 지금의 상황에서 대충 코드의 틀을 잡아보았다.

def 재귀함수():
	if 탈출 조건:
    	정답 출력
        return
    for 내려갈 수 있는 자식 노드들을 순회:
    	if 정답이기 위해 필요한 조건(?): (이 문제로 예를 들면 방문하지 않았을 때)
        	자식 노드로 이동
            재귀함수()
            부모 노드로 이동

이렇게 틀을 잡고 풀었던 것 같다. 백트래킹 문제를 좀 더 풀어봐야겠다.

코드

def back():
    if len(result) == 6:
        print(" ".join(map(str, result)))
        return
    for i in range(k):
        if not checked[i]:
            checked[i] = 1
            result.append(S[i])
            back()
            result.pop()
            for j in range(i + 1, k):
                checked[j] = 0

while True:
    ip = list(map(int, input().split()))
    if ip == [0]:
        break
    k = ip[0]
    S = ip[1:]

    result = []
    checked = [0] * k
    back()
    print()