[백준 알고리즘] 백준 15649번 N과 M (1) 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 15649번 N과 M (1) 파이썬(Python)

1) 문제번호 : 15649번

 

2) 문제 출처

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

15649번: N과 M (1)

 

2. 문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

3. 제약사항

 

 

4. 입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

 

5. 출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

6. 풀이

- 간단한 수열 문제다.

- 재귀로 풀 수도 있고, 라이브러리를 사용해서 풀 수 있다.

 

7. 소스 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split()) # 1부터 N까지, 길이가 M인 수열

# 방문 체크
visit = [0] * N

result = []

def per(idx, N, M) :
    if idx == M : #길이가 M 이라면 출력
        for i in result : # result 리스트에 있는 것들 출력
            print(i, end=" ")
        print()
        return

    for i in range(N) :
        if visit[i]==0 : # 방문하지 않았다면
            visit[i] = 1 # 방문 체크
            result.append(i+1) #경로 넣기
            per(idx+1, N, M) # 순열 돌고
            visit[i] = 0 # 방문 체크 해제
            result.pop()

per(0,N,M)

 

---