백준 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], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램ㅇ을 작성하시오.

 

입력

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

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

 

출력

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

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

 

내 풀🦷

# 6603. 로또
def backtracking(depth, beginwith):
    if depth == 6:
        print(*result)
        return

    for i in range(beginwith, k):
        if not visited[i]:
            result[depth] = nums[i]
            backtracking(depth+1, i+1)
            visited[i] = False


while True:
    lotto = list(map(int, input().split()))
    k = lotto[0]
    nums = lotto[1:]
    result = [0] * 6
    visited = [False] * k
    backtracking(0, 0) // 깊이, 어디서 부터 시작할건지

    if k == 0:
        quit()
    print()

 

N과 M으로 다진 백트래킹 개념을 다른 문제에도 적용시키고 싶어서 로또라는 문제를 풀어보았습니다!!!!

어려웠던 점....

1. 테스트 케이스마다 한줄 뛰우는걸 어떻게 하지....

2. 마지막 0이 나왔을 때 종료를 어떻게 하지...

3. 테스트 케이스의 수가 안주어졌는데 어떻게 하지...

 

 

백트래킹 개념적인부분 보다는 다른것들에 더 시간을 많이 잡아먹었다....

순,조에 대한 개념은 👇👇👇

https://jeniffer0812techstory.tistory.com/94

순열과 조합💪

 

 

참고하면 좋을 개념들 ✍️

• exit() : 프로그램 강제 종료

for i in range(100):
    if i == 5:
        quit()
    print(i)
    
/* 
0
1
2
3
4
*/