[ BOJ / 파이썬 ] 6603. 로또

백트래킹으로 구현했다.

음.. N과M시리즈를 다시 풀어야겠다.

해당 문제에서 시간이 걸리면 안되는데.. 음.. 순간 순열 구현 아이디어가 안 떠올랐다.

해결법은 .. 오름차순인걸 이용해서 새로 넣는 값이 이미 저장한 배열의 마지막 값보다 큰 경우에만 들어가게끔 해줬다.

 

import sys
input = sys.stdin.readline

def make_nums(count, k, data, lotto):
  global visited
  if count == 6:
    print(*lotto)
    return

  for i in range(k):
    if data[i] not in lotto:
      if not lotto or (lotto and lotto[-1] < data[i]):
        lotto.append(data[i])
        make_nums(count+1, k, data, lotto)
        lotto.pop()

while True:
  data = list(map(int, input().split()))
  if data[0] == 0:
    break
  k = data[0]
  make_nums(0, k, data[1:k+1], [])
  print('')