https://www.acmicpc.net/problem/6603
6603번: 로또
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로
www.acmicpc.net
1. 해결방법
"""
1. 아이디어
- 집합 S 원소 중에서 6개를 선택한 모든 경우의 수를 출력해야함.
- while문을 돌려서 입력 리스트를 받고 0이 입력되면 break
- 백트래킹을 이용해서 6개의 원소가 되도록 모든 경우의 수를 구함
2. 시간복잡도
- O(2^k * (k - 6))
3. 자료구조
- 백트래킹 : 재귀
"""
2. 정답코드
입력 예제(1)
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0출력 예제(1)
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34
코드
import sys
input = sys.stdin.readline
answer = []
# recur
def recur(depth, num):
# 재귀 종료 지점
if depth == 6:
print(' '.join(map(str, answer)))
return
# 재귀
for i in range(num, len(s)):
answer.append(s[i])
recur(depth + 1, i + 1)
answer.pop()
# main
while True:
s = list(map(int, input().split()))
if s[0] == 0:
break
# 배열 s의 0번째 삭제
s.pop(0)
recur(0, 0)
print()