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

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

6603번: 로또

 

💡문제 분석 요약

집합 S가 주어졌을 때, 숫자를 사전순으로 k개를 만들 수 있는 모든 경우를 출력한다.

 

💡알고리즘 설계

DFS 문제이다.

1. 입력받은 값이 0일 때 까지 계속 입력받고 dfs를 실행한다

2. 실행 횟수(재귀의 깊이, 현재 숫자의 개수)가 6을 넘어가면 숫자를 출력하고 리턴한다

3. 현재 숫자에서 마지막 숫자까지, 숫자를 추가하고 dfs를 한 후 값이 리턴되면 추가했던 값을 삭제한다.

 

💡코드

import sys
input = sys.stdin.readline

def search(count, idx):
    if count > 6:
        print(' '.join(map(str,answer)))
        return

    for i in range(idx, S[0]+1):
        answer.append(S[i])
        search(count+1, i+1)
        answer.pop()

while True:
    temp=input().rstrip()
    if temp=='0':
        break
    S = list(map(int, temp.split()))
    answer=[]
    search(1, 1)
    print('')

 

 

💡 느낀점 or 기억할 정보

dfs는 append 후 함수를 호출하고, pop한다는 순서만 외우면 풀기 쉬운 것 같다