[ 백준 ] 15651번 : N과 M (3) (파이썬)

문제 )

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

15651번: N과 M (3)

 

[ 풀이 ]

다른 방법으로도 풀 수 있을거 같지만 Backtracking Algorithm을 이용해 푸는 것이 제일 시간이 적게 걸릴거 같아 Backtracking Algorith으로 풀어보았다. 

 

이 문제는 다른 N and M 문제들과 다르게 유망성을 검증할 수 있는 게 없다.
그러므로 promising Function은 굳이 만들필요가 없었다. 

 

< findseq Function의 Algorithm >

✔ 초기화 된 수열 → s
✔ 수열의 index에 접근하는 변수 → num (0부터 M까지)

 

If list s에 M자리까지 숫자가 중복없이 채워진 경우 (수열이 완성된 경우)
           1. 수열 s를 출력
Else
           1. 값을 하나씩 늘려가는 index → i (1~N+1)
                    Ⅰ. s[n]에 i값을 넣어준다.
                    Ⅱ.  index=n+1에 대해 find function시행 

 

- python code 

def findseq(num):
    if num==M:
        print(' '.join(map(str,s)))
    else:
        for i in range(1,N+1):
            s[num]=i
            findseq(num+1)


N,M=map(int,input().split())
s=[0]*M
findseq(0)