[백준] 15650 N과 M (2) (실버3) / 백트래킹

문제요약

나의 코드 및 설명 - 이진트리

• 함수의 변수로 선택할 숫자를 의미하는 selc_num을 주었다.
• 예를 들어 첫 번째 수열의 수로 1을 선택할 것이냐 말 것이냐를 선택하게 하고 이것을 두 개의 하부 함수를 호출하는 방식으로 구현하였다.

def dfs(selc_num, temp_list):
    if selc_num > n:
        if len(temp_list) == m:
            ans.append(temp_list)
        return
    dfs(selc_num+1, temp_list+[selc_num]) #선택
    dfs(selc_num+1, temp_list) #선택x 

n, m = map(int, input().split())
ans = []

dfs(1, [])
for i in ans:
    print(*i)

 

나의 코드 및 설명 - 멀티트리

• 함수의 변수로 선택한 숫자의 개수를 의미하는 index를 주었다.

def dfs(index, s, temp_list):
    if index == m:
        ans.append(temp_list)
        return
    
    for i in range(s, n+1):
        dfs(index+1, i+1, temp_list+[i])
        
n, m = map(int, input().split())
ans = []

dfs(0, 1, [])
print(ans)

피드백

이번 문제는 수열이 중복되면 안되고, 오름차순으로 나타내야 된다는 문제의 조건을 보고 이진트리를 활용하여 문제를 풀 수 있었다.