알고리즘/백준
[알고리즘/백준] N과 M(1) 백트래킹 문제 풀이
레아킴
2022. 5. 29. 18:50
반응형
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
문제 설명
- 1부터 N중 하나를 선택한 뒤
- 다음 1부터 N부터 선택할 때, 이미 선택한 값이 아닌 경우 선택
- M개를 선택 할 경우 프린트
아이디어
- 백트래킹 재귀함수 안에서 for 문 돌면서 숫자 선택 ( 이 때 방문여부 확인)
- 재귀함수에서 M개를 선택할 경우 print
시간복잡도
- N!: 중복이 불가, N = 10까지 가능
자료구조
- 방문 여부 : bool[]
- 선택한 값 입력 배열: int[]
n,m = map(int, input().split())
rs = []
chk = [False] * (n+1). #index와 숫자를 맞추기위해 +1
def recur(num):
if num == m:
print(' '.join(map(str,rs)))
return
for i in range(1,n+1):
if chk[i] == False:
chk[i] = True
rs.append(i)
recur(num+1)
chk[i] = False
rs.pop()
recur(0)
Tip
- 백트래킹 문제는 N이 작음 -> N을 확인하고 백트래킹을 사용할 지 말지 정할 수 있다.
- 재귀함수 사용할 때, 종료 시점 잊지말기!
반응형