[15649] N과 M (1)

 

 

백준 Silver III | 15649 | Python | 문제 링크

문제 설명

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

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

입력

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

출력

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

입출력 예

입력	출력
4 2	1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3

 

나의 풀이

풀이 1

def backtrack(seq, visited):
    if len(seq) == m:
        print(' '.join(map(str, seq)))
        return
    for i in range(1, n + 1):
        if not visited[i]:
            visited[i] = True
            seq.append(i)
            backtrack(seq, visited)
            seq.pop()
            visited[i] = False

n, m = map(int, input().split())
visited = [False] * (n + 1)
backtrack([], visited)

풀이 설명

백트래킹으로 길이 M의 수열을 만든다. 1부터 N까지 순서대로 시도하므로 사전순이 자연스럽게 보장된다.

• visited[i] — 이미 수열에 포함된 숫자인지 추적
• seq.pop()과 visited[i] = False — 재귀 호출 후 상태를 원래대로 복원(백트래킹)
• len(seq) == m — 수열 길이가 M에 도달하면 출력하고 복귀

풀이 2

from itertools import permutations

n, m = map(int, input().split())
for p in permutations(range(1, n + 1), m):
    print(' '.join(map(str, p)))

itertools.permutations는 입력 순서를 기준으로 사전순 순열을 생성한다. range(1, n + 1)이 오름차순이므로 별도 정렬 없이 조건을 충족한다.