[백준] 15663 파이썬(python) : N과 M (9) - (★)

15663번 : N과 M (9)

 

 

import sys
n, m = map(int, sys.stdin.readline().split())
number = list(map(int, sys.stdin.readline().split()))
number.sort()
res = []
visit = [False]*10001
def backTracking(depth):
    if depth == m:
        print(*res)
        return
    overlap = 0 #1
    for i in range(len(number)): #2
        if not visit[i] and overlap != number[i]:
            res.append(number[i])
            visit[i] = True
            overlap = number[i] #3
            backTracking(depth+1)
            visit[i] = False
            res.pop()
backTracking(0)

 

이전 문제와 다르게 재귀호출시 인덱스를 늘리는것이 아닌 방문리스트를 사용

 

#1 : 같은 깊이 안에서 바로 직전에 result에 넣어줬던 숫자와 같으면 넣지 않도록 하는 변수

재귀호출을 하면 다시 0으로 초기화

#2 : for ans in answer:로 이전 문제처럼 처리하고 싶었으나 같은 숫자를 출력해야 하는데 visit[ans]로 처리하면 같은 숫자를 출력하지 못한다.

#3 : 직전의 숫자와 같은 정수 출력 못하도록 answer[i]로 입력

 

중복방지를 위한 overlap 변수를 만든다는 발상이 대단하다.