해커를 꿈꾸는 개발자

파이썬 / BOJ 백준 / 15651번 N과 M(3) - 백트래킹

https://www.acmicpc.net/problem/15651

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 M개를 고른 수열
- 같은 수를 여러 번 골라도 된다.

풀이

1. 백트래킹을 이용하여 풀 수 있는 문제입니다. 백트래킹의 가장 기초적인 문제라 할 수 있습니다. 15649의 문제에서 약간 변형된 문제입니다.

https://zidarn87.tistory.com/329

2. 중복을 허용하기 떄문에, for문에서 중복을 확인하는 if문이 삭제되었습니다.

전체 코드

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

def dfs(cnt):
    if cnt - 1 == M:  # 탈출 조건
        print(' '.join(map(str, lst)))
        return

    for i in range(1, N+1):
        lst.append(i)
        dfs(cnt+1)
        lst.pop()
dfs(1)