Categories
Algorithm🧩
백준 📝
BookReview📕
CleanCode✨
Network 📨
Database 🗄
DevOps☁️
에러 일기📕
Etc💬
Fishy Fish 🎣
Spring🌱
[백준] 15649 N과 M (1)
백준 15649 N과 M (1)
문제
자연수 N과 M이 주어졌을 때 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
입력
- 첫 번째 줄: N, M
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열 출력
해결 방식
백트랙킹 : 해를 찾는 도중 해가 아니라면 다시 돌아가 해를 찾아가는 기법
dfs를 적용하는 알고리즘 방식-
해를 찾는 도중 지금 선택한 경로가 해가 되지 않는다면 해당 경로는 더 이상 돌지 않는다.
→
가지 치기방식 - 가지치기를 얼마나 잘하느냐에 따라 효율성 결정
예시
n = 4, m = 2
-
1부터 탐색 시작
[1] → [1, 2] → [1] → [1, 3] → [1] → [1, 4] → [1] → []
-
이런 방식으로 4까지 모든 조합을 찾아 출력한다.
코드
n, m = map(int, input().split())
s = []
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n+1):
if i in s:
continue
s.append(i)
dfs()
s.pop()
dfs()
