[백준] N과M(1)(15649번)

[출처] https://www.acmicpc.net/

문제

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

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

입력

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

출력

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

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

예제 입출력

접근 및 코드

굉장히 심플한 문제였다.
1~n까지의 자연수 중에서 중복없이 M개를 고른 수열을 구하는 문제로, 예제를 보면 순서에 상관있게 뽑아야 한다.

이 경우, permutation을 이용해서 쉽게 풀수도 있지만, 재귀를 이용해서 풀어보았다.

전역변수로 수를 담을 리스트를 하나 정의한다.

1부터 반복을 돌면서, 숫자가 중복되면 안되기 떄문에 수를 담을 리스트안에 해당 숫자가 있는지 확인한다.
없다면, 리스트에 수를 하나 넣고, 다시 자기 자신을 호출해주고, 리스트가 목표길이인 m에 도달했을떄, 출력을 하고 return해서 종료하게 하면 된다.

이때 자기 자신을 호출하고, 다음 수열을 구하기 위해서 리스트에 넣어주었던 원소를 pop 해주는것을 잊으면 안된다.

코드는 다음과 같다.

import sys


'''입력'''

n,m = map(int,sys.stdin.readline().split())

result = []

def num()-> None:

    if len(result) == m:
        print(' '.join(map(str,result)))
        return


    for i in range(1,n+1):
        #숫자가 안겹쳐야 되므로 확인함,
        if i not in result:
            result.append(i)
            num()
            result.pop()

num()

결과

재귀연습하기에는 N과M 시리즈만한게 없는것 같다.