[백준(Baekjoon)] 15652 N과 M(4)

문제

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

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

 

출력

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

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

 

 예제를 보시려면 더보기를 눌러주세요.

 

입력	출력
3 1	1 2 3
4 2	1 1 1 2 1 3 1 4 2 2 2 3 2 4 3 3 3 4 4 4
3 3	1 1 1 1 1 2 1 1 3 1 2 2 1 2 3 1 3 3 2 2 2 2 2 3 2 3 3 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(start):
    if len(temp) == m:
        print(*temp)
        return
    for i in range(start, n):
        temp.append(nlist[i])
        nm(i)
        temp.pop()

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

 

---

풀이 과정

N과 M(4)문제 조건은 다음과 같다. 

• 같은 수를 여러 번 골라도 된다. -> 3번 문제 조건
• 고른 수열은 비내림차순이어야 한다. -> 2번 문제 조건(오름차순) + 3번 문제 조건(같은 수 여러번 포함)

따라서 이번 문제는 N과 M(2), N과 M(3) 문제의 조건이 합쳐져있는 문제이다.

 

<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

 

 

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

 

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

 

출력에 1 1이 있음 - '같은 수를 여러 번 골라도 된다.' 라는 조건 -> 데카르트의 곱(product)

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

 

---

 

• 코드 1에 필요한 문법

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

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

하지만 product를 사용한 코드 1은 시간 초과 나왔다.

product를 사용하여 모든 경우의 수를 다 구한 다음 비내림차순 확인하여 제거하기 때문에 시간이 많이 걸린 듯 하다. 

 

---

• 코드 2 풀이 과정

아래 예시 그림을 보면서 코드를 이해하면 좀 더 쉽게 이해 할 수 있다.

 

<input : 4 2> 인 경우 

※ start부터인 이유 

순서를 고려하지 않는 문제이기 때문에 선택된 숫자의 이전 숫자들은 고려할 필요가 없다.

 

 

<main 함수>

 

1. m == 1 확인

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

 

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

 

<nm 함수>

 

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

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

 

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

 

3. for문 (start부터 n-1까지)

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

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

3-2. nm(i+1) 호출 : 다음 숫자 선택하기 위해 재귀 함수 호출 (매개변수 : 현재 인덱스)

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

 

---

 

문제 출처

15652번: N과 M (4)