[백준] 파이썬 15666번 : N과 M (12)

https://www.acmicpc.net/problem/15666

15666번: N과 M (12)

백준 15666번: N과 M (12) 파이썬 풀이

 

 

n, m = map(int, input().split())
num = list(map(int, input().split()))

set_num = list(set(num)) # set를 적용하여 중복 제거
set_num.sort()


dict = []

def backtracking(idx):
    global dict
    
    if len(dict) == m : #dict에 들어간 숫자 개수가 m과 같아지면 프린트
        print(*dict)
        return
        
    for i in range(idx, len(set_num)): #시작 인덱스부터 끝까지 반복한다
        dict.append(set_num[i]) #순서대로 해당 숫자를 dict에 넣음
        backtracking(i) 
        dict.pop() #다른 조합도 확인하기 위하여 현재 숫자는 pop
        
backtracking(0)

 

 

처음 N과 M 시리즈를 풀 때 아무생각없이 itertools permutations 쓰려고 했는데 아무리 생각해도 그렇게 푸는게 나올 거 같지는 않아서... 머리를 좀 쓰다가 찾아봤다. 전형적인 백트래킹 문제라는 것을 깨달음..

몇문제는 헤매다가 이 문제를 풀었다. 백트래킹 이론 공부할때도 어려웠는데 ㅜㅜ

 

코드를 차례대로 설명하기는 어려울 거 같아서 주석을 달아놨다.

이해하기 어렵다면 중간중간에 set_num[i]도 프린트해보고, dict도 프린트해보면 이해가 쉬울 듯 하다.

 

코딩은 하면 할 수록 어렵다는 것을 깨닫는다.