[백준, 파이썬] 15664번 N과 M(10)

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

15664번: N과 M (10)

유명한 N과 M 시리즈이다. 

이 문제는 앞에서 포스트한 N과 M(8)번 문제의 연장선이다.

이 문제에서 중요한건 dfs를 이용하여 필요한 경우의 수를 탐색한 후 결과값으로 출력하는 것이다 

 

즉, 핵심 알고리즘 부분은 for문에서 index 범위를 지정하여 탐색하는 부분이라 할 수 있다. 

우선 코드는 다음과 같다. 

 

# 엔과 엠 (10) n,m = map(int,input().split(' ')) number = list(map(int,input().split(' '))) number.sort() array = [] result = [] def solve(level, index): if level == m: a= ' '.join(map(str,array)) if a not in result: result.append(a) print(a) return for i in range(index, n): #핵심 부분 array.append(number[i]) solve(level+1, i+1) array.pop() solve(0,0)

앞서 포스트한 N & M(8)서는

solve(level+1, idx) -> 탐색을 하고 해당 idx를 넘어가지 않고 그대로 input으로 두어 탐색할 수 있게 하였다면 

이번 포스트에서는 solve(level+1,idx+1) 로 지정하여 한번 탐색한 경우는 다시 고려하지 않고 넘어가는 식으로 구현하는것이 차이라고 볼 수 있다. 처음에 풀때 input 문자열을 굳이 int형으로 지정하여 문제를 풀었었는데 그럴필요없이 str 자료형으로 문제를 해결하면 될듯하다.