알고리즘 문제 풀이
[백준 6603번] 로또 - 파이썬
진!!!!!
2024. 2. 17. 21:43
https://www.acmicpc.net/problem/6603
6603번: 로또
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로
www.acmicpc.net
💡문제 분석 요약
집합 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한다는 순서만 외우면 풀기 쉬운 것 같다