9. 로또
- 독일 로또는 {1~49}까지
- 로또를 고르는 가장 유명한 전략 49가지 수 중 k개의 수(k>6)를 골라 다음 수만 가지고 번호 선택
- 집합 s와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램 작성
- 이 때 출력은 사전 순으로 출력한다.
주의해야할 점
- list를 고집할 필요가 없다.
- list인 경우, 해당 원소를 삭제해주고 다시 맞게 껴주는 작업을 하기가 어려우며, 그 경우 역시 값을 빼는 게 아닌 combinations를 6으로 돌림으로써 값이 있는지 찾아주면 된다.
- 문자열로 하면 더 간편하다.
from itertools import combinations as co
from sys import stdin
input = stdin.readline
while(True):
arr = input().split()
if arr.pop(0) == '0':
break
for arr in co(arr, 6):
print(" ".join(arr))
print()
백트래킹을 이용한 풀이
def DFS(s):
if len(result) == 6:
print(" ".join(map(str, result)))
return
for i in range(s, T):
if arr[i] not in result:
result.append(arr[i])
DFS(i)
result.remove(arr[i])
while(True):
arr = list(map(int, input().split()))
T = arr.pop(0)
if T == 0:
break
result = []
DFS(0)
print() # 출력형식에 주의하자
참고자료