21.04.12 알고리즘 공부 22일차

1. N과 M (1) - 백준

 

해결 방법 :

백트래킹

 

이유 : 

DFS의 백트래킹을 사용해야됨. 키워드는 들어왔는지를 확인하고, 추가해주고, 검사하고, 다시 빼주는 것을 재귀처럼 계속 돌리면서 원하는 값이 나올때까지 brute force를 하는데 가지치기를 좀 한 방법인듯

 

참고 자료 :

jamesu.dev/posts/2020/04/13/baekjoon-problem-solving-15649/

백준 문제 풀이: 15649 - N과 M (1)

leejunggae.tistory.com/19

백준 15649번 [Python] 문제풀이 (N과 M(1)) - 이정개

 

문제 : 

www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

 

n, m = map(int, input().split())

def f(s):
  if len(s) == m:
    print(' '.join(map(str, s)))
    return

  for i in range(1, n + 1):
    if i in s:
      continue
    f(s + [i])

f([])

 

---