문제링크
https://www.acmicpc.net/problem/6603
6603번: 로또
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로
www.acmicpc.net
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
import sys
input = sys.stdin.readline
def bf(cnt,start, case,tmp):
if cnt == 6:
print(*tmp)
return
else:
for i in range(start,len(case)):
if case[i] not in tmp:
tmp.append(case[i])
bf(cnt+1, i+1, case, tmp)
tmp.pop()
while True:
case = list(map(int, input().split()))
if case[0]==0:
break
else:
bf(0,0,case[1:],[])
print()
|
cs |
POINT
- 브루트포스
- bf(cnt,start, case,tmp) 를 재귀적으로 사용하였다.
cnt: 현재까지 선택한 수의 갯수 -> 6개 선택하면 끝!
start : 지금 상태에서 고르기 시작할 수
case : 테스트 케이스(전체 후보 숫자 리스트)
tmp : 현재까지 선택한 수의 리스트
조합combination으로 수를 선택해야하기 때문에 리스트에 다음으로 추가할 수는 이미 선택한 수보다 커야한다. 따라서 start라는 변수를 사용해서 이전 index보다 더 큰 index부터 다시 재귀가 시작될 수 있도록 구현했다. 테스트 케이스 배열 case가 이미 오름차순으로 정렬되있기에 index가 클수록 더 큰 수를 의미한다. 재귀 종료조건을 6개 숫자를 전부 선택했을 때이다.
'Algorithm > Baekjoon' 카테고리의 다른 글
| [백준] 14889 스타트와 링크 파이썬 python (0) | 2022.02.25 |
|---|---|
| [백준] 10971 외판원 순회2 파이썬 python (0) | 2022.02.23 |
| [백준] 10819 차이를 최대 파이썬 python (0) | 2022.02.22 |
| [백준] 10974 모든 순열 파이썬 python (0) | 2022.02.22 |
| [백준] 10973 이전 순열 파이썬 python (0) | 2022.02.20 |