6603번: 로또

6603번: 로또

 

백트래킹 문제다.

 

1~45까지의 숫자 중 6보다 큰 N개의 숫자를 고른다.

고른 N개의 숫자 중 6개를 고르는 경우의 수를 모두 출력하면 되는 문제.

 

N과M 문제중, 중복되지 않고, 오름차순으로 숫자를 출력하는 경우와 동일한 문제라고 생각했다.

 

---

# 6603번: 로또
import sys
input = sys.stdin.readline

def backTracking(num):
    if len(result) == 6:
        print(*result)
        return
    
    for i in range(num, cnt):
        result.append(arr[i])
        backTracking(i + 1)
        result.pop()

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

    if line_input[0] == 0:
        break

    cnt = line_input[0]
    arr = line_input[1:]

    result = []

    backTracking(0)
    print()

 

처음에는 visited 배열을 이용해서 중복을 제거해줄까? 라는 생각을 했지만

생각해보니 for반복문의 시작에 backTracking 함수의 파라미터인 num을 넣어주면 자연스럽게 중복이 발생하지 않으므로

굳이 사용할 필요가 없다.

 

역시 백트래킹은 계속 풀어야 익숙해질 것 같다.