알고리즘 백준 15652 N과M(4)(파이썬)

알고리즘 백준 15652 N과M(4)(파이썬)

백준 파이썬 N과M(4)

백준 N과M(4) 파이썬

 

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

출력

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

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

 

 

코드

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


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




if __name__ == '__main__':
    import sys

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

 

코드설명

0) N과M(4) 가 1,2,3 과 다른점은 중복을 허용하고 비내림차순으로 해야한다는 것이다 -> 2,1 같은 것이 안됨

 

0-1) 그래서 우선 backtracking(i+1) 을 해보았더니 큰 숫자들만 출력되서 2,2 같은 것들이 출력되지않았다

 

0-2) 그러면 재귀를(backtracking)을 호출할때 스택의 첫번째수가 2라면 1일 경우의 수를 확인 안하게 2부터 돌게하면 되겠다는 생각을 하여 backtracking의 파라미터로 i를 주게되었다

 

 

그 밑에 코드는 전의 포스팅과 동일!

 

 

깃허브

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