[백준/15650] N과 M (2) (with 파이썬)

✔ 문제

---

✔ 풀이

import sys
input = sys.stdin.readline

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

def dfs(x):
    if len(res) == m:
        print(' '.join(map(str, res)))
        return

    for i in range(x, n+1):
        if i not in res:
            res.append(i)
            dfs(i + 1)
            res.pop()
dfs(1)

---

✔ 설명

재귀함수를 이용해서 풀 수 있다.

for문에서 (시작, n+1)까지를 범위로 잡아 dfs를 돌면 된다.

 

ex) dfs(1) > res[1] 

                           > dfs(2) > res[1, 2]

                                              > dfs(3) > len(res) == 2 이므로 print, return

                          > pop() > res[1] > res[`, 3]

이런 흐름으로 진행된다.

---

✔ 후기

문제 보면서 dfs도 될 것 같다고는 느꼈지만 dfs로도 된다!

굳이 itertools 사용 없어도 dfs로 간단하게 풀 수 있었다.

 

참고:

https://jiwon-coding.tistory.com/22

[백준] 15650번 N과 M(2) / 파이썬(python)