6603번 로또

이 문제는 백트래킹을 이용한다.

 

문제풀이

 

예시와 같이 

7 1 2 3 4 5 6 7 으로 n이 입력을 받았다면 

n에 방문했는지 확인하기 위해 visit 배열을 생성한다. 현재 아무도 방문하지 않았기 때문에 0의 값들을 가진다.

 

그다음 lotto함수가 처음 실행되었을때

처음에는 모두 방문하지 않았기 때문에 if문을 실행하지 않고 입력을 실행한다.

먼저 7은 k이기 때문에 제외하고 1부터 입력이 되고 1은 방문을 안했기때문에 방문을 해서 1의 값을 입력 후에

다음 재귀로 넘어간다. 그다음 재귀에서 똑같이 방문을 하지 않았기 때문에 같은 행동을 진행하고 재귀로 넘어간다

첫번째 재귀는 아무도 방문되지 않았기때문에 1,2,3,4,5,6 이 입력되어 6개를 충족하기 때문에 경우의 수를 출력해준다.

이제 출력후에 리턴으로 재귀를 빠져나와서 그 다음 숫자를 실행하는데, 끝부분의 6의 값부터 보면 이미 값은 방문 했으니 1의 값을 0으로 바꿔 6의 값이 이미 방문을 했다는 것으로 알 수 있게 한다. 그래서 그 다음 for문이 진행될때 그 다음 인수 인 7이 방문되지 않아 입력되어서 출력하면 두번째 경우의 수를 출력할 수 있다.

이런 식으로 방문되었던 인수들을 제외하며 출력되는 방식인데

0의 값을 가졌던 인수가 다시 출력되어야 하는 경우도 있다. 예를 들어 

1 2 3 4 6 7 경우의 수는 이전의 경우의 수때 6, 7이 0의 값을 가지고 방문을 했지만 다시 출력을 해야한다.

그래서 재귀를 빠져나왔을때 다시 사용되어야 하지 때문에 방문값을 안했다는 의미의 0으로 바꾸어 진행하면 된다.

 

코드

 

import sys
def lotto(s, end):
    if end == 6:
        for i in range(k):
            if visit[i]:
                print(n[i], end=' ')
        print()
        return
    for i in range(s, k):
        if visit[i] == 0:
            visit[i] = 1
            lotto(i+1, end+1)
            visit[i] = 0
while True:
    n = list(map(int, sys.stdin.readline().split()))
    if n[0] == 0: break
    k = n[0]; visit = [0 for _ in range(k)]
    del n[0]
    lotto(0,0)
    print()