[백준] 15657번: N과 M (8) - Python

링크: https://www.acmicpc.net/problem/15657

15657번: N과 M (8)

아이디어

• 백트래킹을 이용해 고르는 경우의 수를 찾자
• m개가 골라졌을 때 고른 수를 print하고 return
• 백트래킹의 인자로 고른 수의 인덱스 번호를 넘겨주어 그 인덱스 번호부터 n번째 수 사이에서 또 선택하게 설계
• 위 논리를 적용하는 이유는 비 내림차순으로 하기 위함이니 입력받은 수를 오름차순 정렬해주어 백트래킹 시작

구현

import sys


def back(inx):
    if len(tmp) == m:
        print(" ".join(list(map(str, tmp))))
        return
    for i in range(inx, n):
        tmp.append(li[i])
        back(i)
        tmp.pop()


input = sys.stdin.readline

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

li = list(map(int, input().split()))
li.sort()

if m == 1:
    for i in li:
        print(i)
    exit()
tmp = []
result = []
back(0)

마무리

• N과 M문제는 가볍게 백트래킹 상기시키는 용도로 참 좋은듯 하다.
• 어렵지도 않고