파이썬으로 풀어보는 백준 15649번 N과 M

Python/문제풀이

by 코딩하는 낙타 2020. 1. 15. 20:06

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

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

www.acmicpc.net

재귀를 이용한 풀이:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

n, m = map(int, input().split())
 
check = [False] * (n + 1)
a = [0] * m
 
 
def go(index, n, m):
    if index == m:
        for i in range(m):
            print(a[i], end=' ')
        print()
 
        return
    for i in range(1, n + 1):
        if check[i]:
           continue
        check[i] = True
        a[index] = i
        go(index + 1, n, m)
        check[i] = False
 
 
go(0, n, m)

# 1부터 n까지의 숫자를 이용해 m자리의 수열 만들기
 
# 0은 사용안할것이고 1부터 n+1까지 check(중복으로 사용하는가의 여부)
# a는 m자리 수열 만드는 용도
 
# index, 숫자, 자리 => 다음 수 만들기 함수
# m자리 수열을 다 체웠다면
# i를 0부터 m-1까지
# 출력 a[0] a[1] a[2] ... a[m-1]
# 줄 넘기기
 
# 함수 끝내기
# i를 1부터 n까지
# 만약 i를 이미 사용했다면
# for문을 진행해서 사용할 숫자 바꾸기
# 사용하지 않았다면 i를 사용할 예정이기 때문에 True로 바꾸기
# index 자리에 i 넣기
# index+1 자리 체우기


 

'Python > 문제풀이' 카테고리의 다른 글

백준 2108번: 통계학 (0)	2020.01.17
파이썬으로 풀어보는 백준 9663번: N-Queen (0)	2020.01.15
파이썬으로 풀어보는 백준 11650번, 11651번: 좌표 정렬하기 (0)	2020.01.15
(Python) 문자열에서 모음 지우기 (0)	2020.01.14
파이썬으로 풀어보는 백준 2798번: 블랙잭 (0)	2020.01.10