[Python] 파이썬 백준(15649) N과 M(1)

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

15649번: N과 M (1)

---

나의 풀이

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

3 1

1
2
3

---

4 4

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

백트래킹 알고리즘을 통해 문제를 해결하고자 하였음

import sys
n, m = map(int, sys.stdin.readline()[:-1].split(' '))
answer = []
def pop():
    if len(answer) == m:
        return print(' '.join(map(str, answer)))
    for i in range(n):
        if i+1 not in answer:
            answer.append(i+1)
            pop()
            answer.pop()
pop()

• 첫 번째 요소에 1이 들어왔을 때 answer에 없으니 1을 넣고 pop()을 실행함
• 두 번째 요소에 1이 들어오면 answer에 있기 때문에 2로 넘어감
• 두 번째 요소에 2가 들어오면 answer에 없으니 2를 넣고 pop()을 실행함

위와 같은 프로세스를 진행하여 문제를 해결함