[Python][백준] 6603. 로또 / 백트래킹,재귀,조합 (S2)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

def dfs(n,idx):
    if n == 6:
        print(*rs)
        return
    
    for i in range(idx,K):
        rs.append(lst[i])
        dfs(n+1,i+1)
        rs.pop()

while True:
    lst = list(map(int,input().split()))
    K,lst = lst[0],lst[1:]
    rs = []
    if K == 0 : break
    dfs(0,0)
    print()

 

1. Itertools로 간단하게 풀 수 있지만, 라이브러리를 배제하고 풀어보자.

 

2. 흔한 백트래킹 방식으로, 한가지 주의 할 것은 매개변수로 넘겨주는 값들이다. 

(전반적인 백트래킹의 코드 구조는 동일하다.)

 

재귀부분이 헷갈릴 수 있는데, 

쉽게 말하면 위의 재귀 함수는 아래와 같은 의미이다.

for i in range(10):
    for j in range(i+1,10):
        print(i,j)

 

반대로 이 이중 for문을 재귀로 바꾸면 위의 재귀 함수 형태가 나타난다.

 

 

📌  문제 코멘트

흔한 백트래킹 방식인데, 막상 문제의 조합을 구하기는 어려웠다.

특히 재귀 함수를  너무 구체적으로 파고들면, 진짜 끝도 없이 어려워진다.

(여기에서 멘탈 나감...)

 

재귀함수에 조합을 할 때 헷갈리는데, 

이럴때 먼저 for문을 통해 간단히 구현해보고,

이 for 문 구조를 재귀 함수에 적용하면 좀 더 수월 할 것이다 !

---

📚문제

독일 로또는 {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