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

 

 

15650번: N과 M (2)

 

문제

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

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

 

문제풀이

n,m = list(map(int,input().split()))
s=[]
def dfs(start): #01
    if len(s)==m: #02
        print(' '.join(map(str,s)))
        return
    for i in range(start,n+1): #03
        if i not in s:
            s.append(i)
            dfs(i+1)
            s.pop()
dfs(1)

- 백트래킹 기법을 이용하여 문제를 풀이한다.

 

- #01 : dfs 함수는 시작값을 입력받는다.

- #02 : 리스트 s의 길이가 m가 같으면 출력을 하고 리턴한다.

- 하지만 처음은 s에 들어있는 값이 없으므로, 실질적으로 for문을 기점으로 시작한다.

 

- #03: for문에서 i값은 start부터 n까지 1씩 증가한다. 그리고 리스트 s안에 i가 없으면 s에 추가한다.

- #03: 즉 문제의 조건대로 중복 없이 수열을 만드는 것이다.

- #03: 이후 dfs(i+1)을 사용하여 m과 len(s)가 같아질 때까지 계속해서 값을 추가하다가 같아지면

- #03: 값을 출력하고 리턴하여 s.pop()으로 돌아가 맨 뒷 값을 제거하고 다시 m==len(s)가 되기 위해

- #03: 다음 값을 s에 추가하여 다시 m==len(s)를 만족시켜 수열을 출력하게 된다.

 

- 여기서 start값이 주어져서 for문의 시작값이 되기에 수열이 오름차순으로 작성되는 것이다.