[백준/python] 15649: N과 M(1)

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

15649번: N과 M (1)

 

n,m=map(int,input().split())
def Dfs(arr):
    if len(arr)==m:
        print(' '.join(map(str,arr)))
        return




    for i in range(1,n+1):
        if i not in arr:
            arr.append(i)
            Dfs(arr)
            arr.pop()
se=[]
Dfs(se)

중복없이 골라야 하는게 핵심이다.

백준을 보니 n과m 이라고 써진 문제가 매우 많았는데 순열 또는 조합에 관련되있는듯 싶다.

재귀로 풀어야하나,반복문으로 하려면 어떻게 구현하지 매우 오랜시간을 고민하다가 결국 깃북을 참고했다.

한번 참고하니 나머지 n과 m은 문제에 조건을 보고 종이에 구상을 해보며 살짝씩 코드를 변형하니 수월하게 풀렸다.

수를 se라는 리스트에 넣어주는데 리스트 길이가 m에 다다르면 return을 한다.

여기서 pop이소환되는데

이과정이 도무지 이해가 가지않아 순열 재귀함수 관련 유튜브를 4개정도 뒤졌다.

그냥 외우라는 영상도 있었고 다른영상에서는

재귀를 for문 형식으로 늘리다보니 pop이 왜 저자리에 위치해있는지 보여주었는데 그걸 보고 이해할수있었다.

가급적 빠르게 여러가지의 정렬방법들, 재귀함수 이 두가지라도 능숙하게 사용하는 수준에 다다르고 싶다.