15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
나의 풀이
- 백트래킹 유형 기본 문제라고 하는데, 어려워서 풀이를 참고하면서 풀었다.
- 원소 사용 여부를 저장하는 것이 핵심이었다.
def get_num(k):
# 수열이 완성된 경우
if k == m:
print(*num_list)
return
# 수열에 원소 저장
for i in range(1, n + 1):
if not isused[i]:
num_list[k] = i
isused[i] = 1
get_num(k + 1)
# 사용 후 제거
isused[i] = 0
def solution(n, m):
# 숫자 중복 여부 확인
global isused
isused = [0] * (n + 1)
# 현재 수열
global num_list
num_list = [0] * m
get_num(0)
n, m = map(int, input().split())
solution(n, m)참고
[실전 알고리즘] 0x0C강 - 백트래킹
이번에는 백트래킹을 배워보도록 하겠습니다. 백트래킹도 재귀와 더불어 많은 사람들이 고통을 호소하는 알고리즘 중 하나이지만 의외로 그 재귀적인 구조에 매료되어서 참재미를 알아버리는
blog.encrypted.gg