[백준 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가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

---

풀이

재귀를 통해 개수가 6인 순열을 S집합을 통해 만들고 출력하려한다.

<N과 M (4) 풀이>

def recursion(idx,N,M,start):
    if idx==M:
        print(*p)
        return
    for i in range(start,N+1):
        p[idx] = i
        recursion(idx+1,N,M,i)

위와 같이 재귀함수 내에 반복문과 start변수를 통해 오름차순 순열을 구현할 수도 있지만 시간복잡도가 O(N!)이 나오게 되고 이번 문제는 여러 배열을 입력받고 처리함으로 다른 방법으로 구해보기로 했다

 

def recursion(S,idx,pointer):
    if idx==6:  # 출력조건
        print(*p)
        return
    if pointer >= len(S):   # 인덱스를 계속 채택하지 않을 경우 예외처리
        return
    p[idx] = S[pointer]
    recursion(S,idx+1,pointer+1)    # 인덱스를 채택한 경우
    p[idx] = 0
    recursion(S,idx,pointer+1)  # 채택하지 않은 경우

출력조건으로 인덱스가 6이 되면 출력 후 반환해준다

집합의 앞쪽 인덱스부터 하나씩 채택하는 경우 / 채택하지 않는 경우를 고려하여 재귀한다

 

해당 인덱스를 채택 한 경우 인덱스 번호를 늘리고, 집합의 다음 인덱스를 가리키는 pointer도 1 늘려서 전달한다

해당 인덱스를 채택하지 않은 경우 인덱스 번호는 늘리지 않고 pointer만 늘려서 전달한다

즉, S[i]을 사용하는 경우와 사용하지 않는 경우를 함께 재귀시킨다.

 

만약 S[0]부터 S[k]까지 반복해서 채택하지 않는 경우 idx는 증가하지 않고 pointer만 증가하므로 집합의 길이와 pointer를 비교하여 예외처리를 해준다

시간복잡도는 O(2^k)가 나올 듯 보인다

 

while True:
    arr = list(map(int,sys.stdin.readline().split()))
    k = arr[0]
    S = arr[1:]

    if k==0:
        exit(0)

    recursion(S,0,0)
    print()