코딩테스트/백준
[백준] 15650번 N과 M(2) / 파이썬(python)
Jiwon_C
2021. 3. 12. 03:18
# 문제 링크
15650번: N과 M (2)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
# 관련 알고리즘 이론
백트래킹 (Backtracking)
# 백트래킹 (퇴각 검색) - 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행 - 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다. - DFS(깊이 우선 탐색) 기반 # EXAMPLE -
jiwon-coding.tistory.com
# Soultion
15649번과 거의 동일하지만 이 문제에서는 [1,2], [2,1]과 같은 경우는 중복되는 경우로 보고 [1,2]만 출력해야한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
# 15649
n,m = list(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 not in s:
s.append(i)
dfs()
s.pop()
dfs()
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# 15650번
n,m = list(map(int,input().split()))
s = []
def dfs(start):
if len(s)==m:
print(' '.join(map(str,s)))
return
for i in range(start,n+1):
if i not in s:
s.append(i)
dfs(i+1)
s.pop()
dfs(1)
|
cs |
4. 소스를 보면 알수있듯이 15649번과 동일하지만, start 변수만 추가를 해주었다.
8. 기존에는 1부터 n까지 모든 숫자를 사용했지만 [2,1]과 같이 앞의숫자가 뒤의숫자보다 작은경우를 제외하기위해 start부터 n까지 숫자를 사용한다.
12. 재귀함수를 호출할때는 i를 이용하여 자신의 다음숫자를 부르게된다.
