오늘의 알고리즘 -boj-6603

문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

풀이

주어진 수열에서 6개의 숫자를 고르면 되는 문제다.

문제에서 숫자를 고를 때 "수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다." 라고 되어 있고 수열을 오름차순으로 주어진다고 했다.

이 얘기를 바꿔말하면 수열을 비내림차순 수열을 만드는 거고 수열에 미리 -1을 넣어 초기화해두고 중복되지 않은 값 and 수열의 마지막 값 보다 큰 값만 수열에 들어갈 수 있게 설정하고 depth가 6에 닿았을 때 출력하는 코드를 짰다.

주의할 점은 각 입력에 대한 출력마다 한 칸씩 띄워야 하기 때문에 함수가 종료된 다음 print를 한 줄 넣어주는 것이다.

def backtracking(depth, limit, cur_seq):
    if depth == limit:
        print(*cur_seq[1:])
        return
    
    for number in sequential:
        if number not in cur_seq and cur_seq[-1] <= number:
            backtracking(depth+1, limit, cur_seq + [number])
        

while True:
    cur_input = list(map(int,input().split()))
    if cur_input[0] == 0:
        break
    
    N = cur_input[0]
    sequential = cur_input[1:]
    backtracking(0, 6, [-1])
    print()