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

문제

자연수 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 3 2 4 3 4
4 4	1 2 3 4

---

나의 풀이

[Python(파이썬)]

 

코드 1. itertools, combinations사용

from itertools import combinations
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(combinations(nlist, 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+1)
        temp.pop()
if m == 1:
    print(*nlist, sep='\n')
else:
    nm(0)

 

 

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

---

풀이 과정

 

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

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

 

<N과 M(1)>

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

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

<N과 M(2)>

 

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

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

 

---

• 코드 1에 필요한 문법

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

이 문제에서 필요한 문법은 위의 링크에서 조합(Combinations)이다.

 

 

• 코드 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+1)
        temp.pop()

 

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

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

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

 

 

 

 

---

문제 출처

15650번: N과 M (2)