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

www.acmicpc.net/problem/15650

15650번: N과 M (2)

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

 

입력

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

 

출력

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

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

 

예제 입력 1

3 1

예제 출력 1

1
2
3

 

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 3
2 4
3 4

 

예제 입력 3

4 4

예제 출력 3

1 2 3 4

 

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 백트래킹

 

풀이

1번과 비슷하지만 조합으로 구현하는 문제이다.
이 역시 itertools를 이용하면 쉽게 풀 수 있지만 재귀를 이용하여 구현하는 방법 역시 알고 있어야하기 때문에
2가지 방법으로 구현했다.

itertools combinations 이용

import sys
import itertools

N, M = map(int,sys.stdin.readline().split())

N_list = [i for i in range(1,N+1)]
answer = list(itertools.combinations(N_list,M))

for i in range(len(answer)):
    for j in range(len(answer[0])):
        print(answer[i][j] , end = ' ')
    print()

1번과 큰 차이 없이 combinations를 이용하여 구현하였다.
itertools의 경우에는 1번째 인자로 list와 같은 컨테이너 타입의 변수를 이용하기 때문에 추가적으로 list를 생성해야한다.

재귀 이용

import sys

N, M = map(int,sys.stdin.readline().split())
answer = []
check = [0 for _ in range(N)]

def NandM2(index, start, N, M):
        if index == M:
            for i in range(M):
                print(answer[i] , end = ' ')
            print()
            return

        for i in range(start, N):
            if not check[i]:
                check[i] = 1
                answer.append(i+1)
                NandM2(index+1,i,N,M)
                check[i] = 0
                answer.pop()

NandM2(0, 0, N, M)

조합에 경우에는 순서를 신경쓰지 않기 때문에 중복되는 숫자가 사용되면 안된다. 
즉 반복문을 돌면서 지금 내가 사용한 숫자보다 작은 숫자가 나오지 않게하면 구현할 수 있을 것 같았다.
ex) [2] 1 과 같은 형태

NandM 1번 함수와는 다르게 start라는 변수를 추가하여 반복문의 시작 지점을 지정하여
이전에 사용한 숫자 다음부터 사용되게 구현하니 문제없이 작동하였다.