백준 6603번: 로또 [Python3]

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

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이 하나 주어진다. 

출력

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

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

 

예제 입력 1 

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

예제 출력 1 

1 2 3 4 5 6
1 2 3 4 5 7
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​

---

 <내 풀이>

import sys
input = sys.stdin.readline

def dfs(number):

    if len(array) == 6:   # 로또의 길이가 6으로 제한되어 있다.
        print(*array)
        return

    for i in range(number,K):
        if visit[i] == True:
            continue

        visit[i] = True
        array.append(S[i])
        dfs(i)
        visit[i] = False
        array.pop()


while True:
    input_data = list(map(int,input().split()))

    if input_data[0] ==0:
        break

    K = input_data[0]
    S = input_data[1:]
    array = []
    visit = [False] * K
    dfs(0)
    print("")  # 이 부분을 놓쳐서 출력 오류가 나왔었다.

 

---

<느낀점>

요즘은 계속해서 알고리즘 문제를 풀고있다.

하나의 챕터를 가지고 지속적으로 풀고있는데 최근에는 백트래킹 문제를 계속해서 풀어보고 있다.

처음에 백트래킹 문제를 봤을때는 이걸 어떻게 풀지라는 생각이 들었는데 계속해서 풀어보고 다른사람의 풀이를 보고 이해하려고 해보고 https://pythontutor.com/visualize.html#mode=display 해당 사이트를 통해 재귀 과정을 계속해서 돌려보았더니 이제는 조금씩 이해가 가기 시작했다.