[백준] 6603 로또 python3

문제 : https://www.acmicpc.net/problem/6603

6603번: 로또

 

코드

from sys import stdin
input = stdin.readline


def backtracking(idx, S, result, checked):
    # 다 채웠으면
    if idx == len(result):
        print(" ".join(map(str, result)))
        return

    # 첫 숫자가 조건을 벗어나면
    ## ( 첫 숫자의 최댓값은 주어진 배열 S의 K-6+1 번째 요소)
    if idx > 0 and result[0] > S[len(S)-6+1]:
        return

    # idx 보다 적은 수는 나오지 않음
    for i in range(idx, len(S)):
        if checked[i]: # 체크된건 넘김
            continue

        if result[idx-1] > S[i]: # 전 숫자보다 작다면 정렬이 안됨
            continue

        # 정답 리스트에 추가
        checked[i] = True
        result[idx] = S[i]

        # 다음 idx 로 넘어감
        backtracking(idx+1, S, result, checked)

        # 돌아오면 체크 해제
        checked[i] = False
        result[idx] = -1


def lotto(S):
    checked = [False] * len(S)
    result = [-1] * 6

    backtracking(0, S, result, checked)


while True:
    S = list(map(int, input().split(" ")))
    if S.pop(0) == 0:
        break

    lotto(S)
    print()

 

해설

찾아보니 콤비네이션을 이용해서 푼 사람들도 꽤 보였지만, 나는 연습을 좀 하고 싶어서 백트래킹으로 풀었다.

N과 M 문제와의 차이점은 오름차순 정렬으로 출력해야 한다는 점이었다.

따라서 중간에 정렬을 해치는 요소를 찾으면 그 요소는 넘기는 방식으로 구현해주었다.