[Baekjoon 6603 / Python / 실버2] 로또

문제

 

기본적인 백트래킹 문제이다.

주어진 집합에서 6개 숫자의 조합(순서가 다른 같은 숫자를 중복으로 간주)을 구해야 한다.

 

# 실버2 -> 백트래킹

import sys

input = sys.stdin.readline

def back_tracking(depth, start, result):

    # 6개의 숫자가 모이면 출력

    if depth == 6:

        print(*result)

        return

   

    for i in range(start, len(S)):

        result.append(S[i])

        back_tracking(depth + 1, i + 1, result)

        result.pop()

while True:

    K, *S = map(int, input().split())

    if K == 0: break  # 0이 들어오면 입력의 끝으로 간주하고 반복문 종료

    back_tracking(0, 0, [])

    print() # 입력에 대한 처리가 완료될 때마다 개행

 

6개의 숫자가 모이면 출력해야 하므로, depth가 6이 되면 출력하고 return 하도록 했다.

또한 start 인자를 매 호출마다 1씩 추가하여 전달함으로써, 순서만 바뀐 중복된 숫자가 생기지 않게 했다.

또한 입력은 오름차순이기 때문에 이렇게 할 경우 자동으로 결과가 오름차순으로 출력된다.

 

마지막으로 하나의 입력에 대한 처리가 완료될 때마다, print()를 통해 개행문자를 추가해 주면 된다.

 

결과