[백준] 6603번: 로또 파이썬

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

6603번: 로또

백트래킹이 뭐야?(ㄹㅇ아직잘모르겠음)

백트래킹 문제다.

백트래킹 아직 어렵다..

일단 백트래킹이란 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘을 말한다..

설명만으론 아직 잘 이해가 되지않는다..

바로 풀이 들어갑니다.

풀이

 

앙

일단 arr배열에 입력을 받는다.

arr[0]은 사용되는 수의 개수 , arr[1] ~ arr[arr[0]]은 사용되는 수

 

로또로 뽑은 수를 보관하기 위해 크기가 6인 anwser배열 선언.

사용되는 수 중에서 이미 뽑은 수를 구별하기 위해 크기가 arr[0] + 1 (0번째에는 개수가 들어가니까 +1해야함) 배열선언.

 

백트래킹하는 과정에서 이미 뽑은 수 보다 작은 수는 뽑지않도록 코드작성.. (이 부분이 조금 헷갈렸음)

def func(x):
  global a
  if x == 6:
    for i in range(6):
      print(anwser[i], end=' ')
    print()
    return
  else:
    if x == 0:
      a = 1
    for i in range(a, arr[0]+1):
      if not isused[i]:
        anwser[x] = arr[i]
        isused[i] = True
        a = i
        func(x+1)
        isused[i] = False

while True:
  arr = list(map(int, input().split()))
  if(arr[0] == 0):
    break
  anwser = [0] * 6
  isused = [False] * (arr[0]+1)
  func(0)
  print()