[백준(Baekjoon)] 15651 N과 M(3)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

 

출력

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

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

 

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

---

나의 풀이

[Python(파이썬)]

 

코드 1) itertools,  product(cartesian product; 데카르트 곱)사용

from itertools import product
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(product(nlist, repeat=m)):
        print(*i, sep=' ')

 

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

n, m = map(int, input().split())
nlist = [i for i in range(1, n+1)]
temp = []

def nm():
    if len(temp) == m:
        print(*temp)
        return
    for i in range(n):
        temp.append(nlist[i])
        nm()
        temp.pop()
if m == 1:
    print(*nlist, sep='\n')
else:
    nm()

 

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

---

풀이 과정

백준에 다양한 <N과 M>문제들이 있다.

이 중 앞서 1, 2번은 이미 포스팅했다. 이번 문제와 1, 2번 문제의 차이점에 대해서 우선 알아보자

 

1) <N과 M(1)>문제 : 순열

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

 

출력에 1 2과 2 1이 모두 있음 - 순서를 고려해 나열한 경우의 수인 순열

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

 

2) <N과 M(2)>문제 - 조합

 

[백준(Baekjoon)] 15650 N과 M(2)

 

출력에 1 2는 있고 2 1은 없음 - 순서를 고려하지 않고 나열한 경우의 수인 조합

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

 

 

3) <N과 M(3)>문제 - 데카르트의 곱(product)

 

순열과 조합을 사용한 위의 문제들(N과 M(1), N과 M(2))과 달리 이 문제는 Product를 사용하는 문제이다. 

• '같은 수를 여러 번 골라도 된다.' 라는 조건이 있기 때문이다. 

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

 

---

 

• 코드 1에 필요한 문법

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

이 문제에서 필요한 문법은 위의 링크에서 product(cartesian product; 데카르트 곱)이다.

 

---

• 코드 2 풀이 과정

그림으로 보면 코드 이해가 좀 더 쉬워질 것이다. 

 

<input : 4 2 인 경우>

 

 

 

<main 함수>

 

1. m == 1 확인

m이 1이라면 nlist 원소 바로 출력, 1이 아니라면 nm 함수 호출

 

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

 

<nm 함수>

 

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

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

 

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

 

3. for문 (0 ~ n-1까지)

for i in range(n):
        temp.append(nlist[i])
        nm()
        temp.pop()

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

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

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

 

 

 

 

---

문제 출처

15651번: N과 M (3)