백준 파이썬 15651번 N과 M (3) (Today I Learn 2025.09.11)

백준 파이썬 공부 2025.09.11
15651번 N과 M (3) (실버 3)

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

- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.

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

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

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

4. 문제 풀이
N과 M (1) 문제에 같은 수 중복 가능 조건이 붙은 문제이다
visted 리스트를 n x m 2차원 리스트로 만들어,
1 ~ n 사이의 수를 중복 포함하여 m번 뽑는 방식으로 코드를 작성하였다.

depth 회차의 경우 이전 숫자를 제외한 모든 숫자를 출력 가능하다.

>>코드1. 2차원 리스트 이용

n, m = map(int, input().split())
visited = [[False] * (n+1) for _ in range(m)]
ans = []

def dfs3(depth):
    if depth == m:
        print(*ans)
        return
    
    for i in range(1, n+1):
        if visited[depth][i]:
            continue
        
        visited[depth][i] = True
        ans.append(i)
        
        dfs3(depth+1)
        
        visited[depth][i] = False
        ans.pop()
        
dfs3(0)

근데 곰곰히 생각을 해보니...
중복이 가능하다보니, visited로 방문 즉 중복을 검사할 필요가 없다;;
따라서 그냥 숫자 갯수만 유의하여, 순서대로 출력하면 된다.

>>코드2. visited 삭제 및 간결화

n, m = map(int, input().split())
ans = []

def dfs3(depth):
    if depth == m:
        print(*ans)
        return
    
    for i in range(1, n+1):  
        ans.append(i)
        dfs3(depth+1)
        ans.pop()
        
dfs3(0)

  

5. 문제 링크
https://www.acmicpc.net/problem/15651