알고리즘 백준 15651 N과M(3)(파이썬)

알고리즘 백준 15651 N과M(3)(파이썬)

백준 N과M(3) 파이썬

백준 파이썬 N과M(3)

 

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

코드

def backtracking():
    if len(treeList) == M:
        print(' '.join(map(str,treeList)))
        return
        
        

    for i in range(1,N+1):
        treeList.append(i)
        backtracking()
        treeList.pop()




if __name__ == '__main__':
    import sys

    N,M = map(int,sys.stdin.readline().split())
    printList = []
    treeList = []
    backtracking()

 

 

코드설명

0) N과M (1) (2) 문제와 다르게 (3) 문제는 중복까지 허용하는 문제다

 

0-1) 처음에는 기존코드에서 중복을 체크하는 부분인 if i in treeList 만을 지웠다

하지만 그럴 경우 무한 재귀에 빠지게된다

 

0-2) 그래서 len(treeList) == M 코드가 실행되면 해당 재귀를 끝내고 윗단게로 가게 return(해당 함수를 끝내기) 을 추가해주었다

 

0-3) 그러면 사실 좋은 코드라면 N과M(1) (2) 둘다 return을 넣어야 될거 같다는 느낌이 들었음

 

 

그 밖에 코드는 전 포스팅과 동일하다

 

 

깃허브

https://github.com/developer-hyun/Algorithm-Study/tree/main