[BOJ][Python]15666번 풀이

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

15666번: N과 M (12)

import sys
ssr = sys.stdin.readline

def sol(idx):
    if len(ans) == m:
        print(*ans)
        return
    last = 0
    for i in range(idx,n):
        if last != num[i]:
            ans.append(num[i])
            last = num[i]
            sol(i)
            ans.pop()
        
n,m = map(int, ssr().split())
num = sorted(list(map(int, ssr().split())))
ans = []
sol(0)

어제 풀었던 문제와 거의 동일합니다. 정답률이 꽤 높은 이유는 아마 그래서겠죠. 중복된 수열을 시간초과가 나지 않게 제거하는게 N과 M(9)의 핵심이었는데 그 부분이 해결되면 다른 N과 M문제와 다를게 없으니까요. 덕분에 보자마자 바로 풀었습니다.

 

문제 접근은 당연히 백트래킹입니다. 그리고 인덱스의 시작 위치를 조절하는 테크닉과 중복 수열을 제거하는 테크닉을 둘 다 사용하면 해결되는 문제죠. 다른 N과 M 문제들을 풀어오셨다면 별로 어렵지 않은 문제일 것이고, 이 문제가 처음이라면 어렵다고 느끼실 것 같습니다. 저도 어제 9를 풀 때 그랬으니까요.