728x90
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.
https://www.acmicpc.net/problem/15650
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.
중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제
# input
3 1
# output
1
2
3
# input
4 2
# output
1 2
1 3
1 4
2 3
2 4
3 4문제 풀이
# 입력 받기
N, M = map(int, input().split())
# 정답을 저장할 리스트 초기화
answer = []
def backtracking(num):
# answer의 길이가 M과 같다면 정답을 출력
if len(answer) == M:
print(' '.join(map(str, answer)))
return
# num부터 N까지의 숫자에 대해 반복
for i in range(num, N+1):
# i가 answer에 포함되어 있다면 건너뜀
if i in answer:
continue
# i를 answer에 추가
answer.append(i)
# 다음 숫자에 대해 재귀적으로 백트래킹 호출
backtracking(i + 1)
# answer에서 마지막 요소 제거 (백트래킹 과정)
answer.pop()
backtracking(1)파이썬을 독학하시는 분들에게 도움이 되길 바라며,
혹 더 좋은 방법이 있거나 오류가 있다면 편하게 말씀 부탁드립니다.
728x90
