[백준] 6609 : 로또 - Python(파이썬)

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

6603번: 로또

---

설명

DFS를 이용해 푼 코드이다.

우선 숫자를 입력받는 nums, 결과를 출력하기 위한 res 변수들을 정의한다.

BackTracking 함수를 사용하기 위해 인자로 start(시작 index)와 cnt(길이)를 준다

 

* non-promising 조건

로또 갯수가 6개이면 종료하여야 하므로 cnt == 6 인 경우 return

 

for i in range(start, len(nums)): # 인자로 넘어온 start index 부터 마지막 까지 반복하며

        res[cnt] = nums[i] # res의 최신값을 nums[i]로 할당한 후

        BackTracking(i+1, cnt+1) # 재귀적으로 호출

 

예를들어 1 2 3 5 8 13 21 34 가 입력으로 주어진 경우

1 2 3 5 8 ... 에서 13이 들어온 경우 1 2 3 5 8 13출력하고 return

다시 1 2 3 5 8 에서 13의 다음번째인 21이 들어온 경우 1 2 3 5 8 21을 출력하고 return

이런식으로 반복하면 된다.

 

import sys

def BackTracking(start, cnt):
    if cnt == 6: # 길이가 6이 되면 res를 출력하고 return
        print(*res)
        return

    for i in range(start, len(nums)): # 인자로 넘어온 start index 부터 마지막 까지 반복하며
        res[cnt] = nums[i] # res의 최신값을 nums[i]로 할당한 후
        BackTracking(i+1, cnt+1) # 재귀적으로 호출

while True:
    global res, nums
    nums = list(map(int, sys.stdin.readline().split()))
    head = nums[0]
    if head == 0:
        break
    nums = nums[1:] # 첫번째 원소빼고 다시 nums 정의
    res = [0] * 6 # 결과를 출력하기 위한 변수 초기화
    BackTracking(0,0)
    print()