[백준(Baekjoon)] 15649 N과 M(1)

문제

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

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

 

입력

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

 

출력

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

 

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

 

입력	출력
3 1	1 2 3
4 2	1 2 1 3 1 4 2 1 2 3 2 4 3 1 3 2 3 4 4 1 4 2 4 3
4 4	1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1

---

나의 풀이

[Python(파이썬)]

 

코드 1. itertools, permutation 사용

# v1 - 순열 사용(순서 고려)
from itertools import permutations
n, m = map(int, input().split())
nlist = [i for i in range(1, n+1)]

if m == 1:
    print(*nlist, sep='\n')
else:
    for i in list(permutations(nlist, m)):
        print(*i, sep=' ')

 

 

코드 2. 재귀함수 사용(백트래킹)

n, m = map(int, input().split())
nlist = [i for i in range(1, n+1)]
check = [False]*n   # 중복 check
temp = []

def nm(cnt):
    if cnt == m:
        print(*temp)
        return
    for i in range(n):
        if check[i] == True:
            continue
        temp.append(nlist[i])
        check[i] = True
        nm(cnt+1)
        temp.pop()
        check[i] = False


if m == 1:
    print(*nlist, sep='\n')
else:
    nm(0)

 

• 코드1(첫번째), 코드2(두번째) 메모리와 시간 차이

 

---

풀이 과정

재귀를 학습하려고 푼 문제이기 때문에 내장 함수를 사용하지 않고 재귀를 이용하여 직접 구현해 본 다음 내장 함수 사용 코드도 구현하였다. 

백준에는 많은 [N과 M] 문제가 있다 입력은 같지만 출력이 조금씩 다른 것을 볼 수가 있다. 

출력에 따라 문제를 이해하여 코드 구현을 다르게 해야한다. 

 

<N과 M(1)>

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

입력	출력
4 2	1 2 1 3 1 4 2 1 2 3 2 4 ...

예시의 입력과 출력 일부를 가져왔다. 

출력을 보면 중복 없이 M개를 고른 수열인데 1 2과 2 1이 모두 있는 모습을 볼 수 있다. 

그렇다면 서로 다른 n 개 중 r 개를 골라 순서를 고려해 나열한 경우의 수인 순열임을 알 수 있다. 

 

• ---

  코드 1에 필요한 문법

[Python(파이썬)] itertools - 순열, 조합, product

이 문제에서 필요한 문법은 위의 링크에서 순열(permutations)이다.

 

 

• 코드 2 풀이 과정

그림으로 먼저 이해하면 코드를 이해하기가 더 쉽다.  

 

<input : 4 2> 인 경우

<main 함수>

1. m == 1 확인

m이 1이면 nlist 원소를 바로 출력, 1이 아니면 nm(0) 호출

if m == 1:
    print(*nlist, sep='\n')
else:
    nm(0)

 

<nm 함수>

2.  cnt == m 확인 (cnt = 현재까지 선택된 숫자의 개수, m = 선택해야하는 숫자의 개수)

같다면 temp 원소 출력 후 return, 다르다면 3번 실행

if cnt == m:
        print(*temp)
        return

 

3. for문

for i in range(n):
        if check[i] == True:
            continue
        temp.append(nlist[i])
        check[i] = True
        nm(cnt+1)
        temp.pop()
        check[i] = False

 

3-1. check[i] == True 이면 사용되었으므로 continue, False이면 사용 전이므로 아래 코드 계속 실행

check : 숫자 사용 여부 확인 리스트 (사용 전 : False, 사용 후: True)

3-2.  temp에 nlist[i] 저장 (temp : 숫자 사용 순서 저장)

3-3. check[i] = True 변경

3-4. nm(cnt+1) 호출 : 다음 숫자 선택하기위해 재귀 함수 호출 

3-5. 호출 함수 반환된 다음 temp의 마지막 값 pop 

3-6. check[i] = False변경

---

문제 출처

15649번: N과 M (1)