취준생의 코딩테스트 연습기

[백준] 15651번 N과 M(3) / 파이썬(python) 본문

코딩테스트/백준

[백준] 15651번 N과 M(3) / 파이썬(python)

Jiwon_C 2021. 3. 12. 16:06

# 문제 링크

www.acmicpc.net/problem/15651

 

15651번: N과 M (3)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

# 관련 알고리즘 이론

jiwon-coding.tistory.com/34

 

백트래킹 (Backtracking)

# 백트래킹 (퇴각 검색) - 길을 가다가 이 길이 아닌 것 같으면 왔던 길로 되돌아가 다른 경로로 진행 - 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다. - DFS(깊이 우선 탐색) 기반 # EXAMPLE  -

jiwon-coding.tistory.com

# Soultion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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):
        s.append(i)
        dfs()
        s.pop()
dfs()
 cs

 

이 문제는 15649번과 동일하지만, 중복을 허용하기 떄문에, 10번의 for문에서 중복을 확인하는 if문이 삭제되었다. 

나머지는 15649번 문제와 동일하다.

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 9663번 N-Queen / 파이썬(python) - 도전중  (0) 2021.03.13
[백준] 15652번 N과 M(4) / 파이썬(python)  (1) 2021.03.12
[백준] 15650번 N과 M(2) / 파이썬(python)  (7) 2021.03.12
[백준] 15649번 N과 M(1) / 파이썬(python)  (4) 2021.03.11
[백준] 10814번 나이순 정렬 / 파이썬(python)  (0) 2021.03.11
'코딩테스트/백준' Related Articles more
Comments