[BOJ #15649] N 과 M

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

-> 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

내가 쓰던 코드

import sys; input = sys.stdin.readline
N, M = map(int, input().split())

lst = []

for n in range(1, N+1):
    for nn in range(1, N+1):
        lst.append(n)
        if nn != n:
            lst.append(nn)
            print(lst)
            lst.pop()
        lst.pop()

이런식으로 꿍시렁꿍시렁 쓰고 있었다.. 근데 문제대로라면 입력 받은 M 만큼 for문을 돌려야 하는데,,, 이걸 어케하노..하면서 일단 M=2 짜리 코드를 짬. 근데 어떡해.. 그렇게 짜면 안되는 걸^^ 나으 돌머리는 더이상 굴러가지 않아서 서칭... 한 결과 wowowow~!! 재귀함수 쓰면 됨. 이것이 바로 오늘 배운 백트래킹...wow~ 난 생각지도 못했지~ ^^

 

1) 생각 못했던 재귀함수 쓰고,

2) .join() 도 써서 정답 출력

 

.join() 알고있긴 했어도 잘 안썼었는데, 이 format 기억해서 종종 써먹어야지!

 

내가 쓴 코드

import sys; input = sys.stdin.readline

def nnm():
    if len(lst) == M:
        print(' '.join(map(str, lst)))
        return

    for n in range(1, N+1):
        if n not in lst:
            lst.append(n)
            nnm()
            lst.pop()

N, M = map(int, input().split())
lst = []

nnm()

 

출력 결과

 

제출 결과