난이도

Silver 3

풀이 참고 유무

x

막힌 부분

x

문제

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

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

출력

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

예제 입력

4 2

예제 출력

1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

문제 검토

정렬해주고 방문체크만 잘해주면 될 것 같다.

풀이(python)

Python

from sys import stdin
input=stdin.readline
n,m = map(int,input().split())
num=list(map(int,input().split()))
num=sorted(num)
for x in range(len(num)):
    num[x]=[num[x],False]
result=[]
def dfs(depth):
    if depth==m:        
        print(' '.join(map(str,result)))
        return
    for x in range(len(num)):
        if not num[x][1]:            
            result.append(num[x][0])            
            num[x][1]=True
            dfs(depth+1)
            num[x][1]=False
            result.pop()
dfs(0)            

아이디어:

#리스트를 정렬한다.
#짝지었을 때는 사전순이 아님으로 순서 그대로 출력하면 될 것 같다.

걸린 시간

14:33

총평

N과 M 문제에서 파생된 문제이기도 하고 이전에 풀었던 문제들에서 자주 보았던 방법을 사용하면 금방 풀려서 시간이 적게 걸렸다.