[백준] 6603 파이썬(python) : 로또 - (★)

6603번 : 로또

 

 

조합론을 이용한 풀이)

import sys
from itertools import combinations
while True:
    s = list(map(int, sys.stdin.readline().split())) #1
    k = s.pop(0) #2
    if k == 0: #3
        break
    for tmp in combinations(s, 6): #4
        nums = list(tmp) #5
        nums.sort()
        print(*nums)
    print()

 

#1 : 숫자를 입력받고

#2 : 리스트의 첫번째 원소를 k로 지정(리스트의 pop()메서드는 원소를 뺀 후 자동으로 재정렬)

#3 : 만일 k가 0이면 반복문 탈출

#4 : 리스트 s에서 6개의 숫자를 꺼내는 튜플을 만들고

#5 : 정렬을 위해 튜플을 리스트화 한뒤 리스트 언패킹으로 출력

 

 

백트래킹을 이용한 풀이)

import sys
while True:
    s = list(map(int, sys.stdin.readline().split())) #1
    k = s.pop(0) #2
    if k == 0: #3
        break
    res = []
    def backTracking(depth, idx):
        if depth == 6:
            print(*res)
            return
        for i in range(idx, k):
            if s[i] not in res:   
                res.append(s[i])
                backTracking(depth+1, i+1)
                res.pop()
    backTracking(0, 0)
    print()

 

 

1 2 3 4 5 6 다음 1 2 3 4 5 7 을 출력할 떄 depth는 6이 되고 idx는 7이 되어서 if depth ==  6: 이므로 res를 출력할 수 있다. 그래서 backTracking(depth, idx)로 매개변수를 2개로 나누었고 재귀호출 할때 backTracking(depth+1, i+1)을 해줘 res의 이전 값보다 작은 수는 res의 뒤에 오지 않는다. (number는 오름차순으로 정렬된 입력값을 받음)

 

---

15655번 : N과 M (6)

14889번 : 스타트와 링크