알고리즘 백준 15650 N과M(2)(파이썬)

알고리즘 백준 15650 N과M(2)(파이썬)

백준 N과M(2) 파이썬

백준 파이썬 N과M(2)

 

 

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

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

출력

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

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

 

 

코드

 

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



    for i in range(number,N+1):
        if i in treeList:
            continue


        treeList.append(i)
        backtracking(i+1)   #2)
        treeList.pop()




if __name__ == '__main__':
    import sys

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

 

 

코드설명

 

0) 백준 N과M(1)과 N과M(2)의 차이점은 N과M(2)는 수열이 오름차순이여야 한다는 것이다.

 

0-1) 그러면 N과M(1) 코드에다가 스택에 담긴 전의 수보다 큰 수들만을 재귀로 호출해서 실행시키면 된다

 

0-2) 하지만 해당 코드를 짜며 생각한 점은 N과 M이 4 4 일때는 1 2 3 4 다음에 1 3 4 등을 탐색하는데 어차피 뒷 숫자들은 스택의 길이가 4가 될수없어 탐색하지 않아도 되는 부분이 아닌가 하는 생각이 들긴하였다. 그러면 if문으로 스택의 첫번째값과 두번째값 이후에 값이 오는것의 최대 수가 M보다 작으면 해당 경우의 수를 전부 날리는 if문을 넣어야하나..??

 

 

1) 리스트를 string형태로 출력하기 위해 join함수를 사용하였으며 저렇게 하면 원본리스트인 treeList가 유지된다.

 

 

2) 재귀를 할때 스택에 있는 값보다 큰값만을 돌리기위해 i를 새로운 함수의 파라미터로 받았고 해당 값을 i+1해주었다.

 

 

 

깃허브

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