📘[15650] N과 M (2)

문제

https://www.acmicpc.net/problem/15650

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

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

답안

import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
n_arr = [i for i in range(1, n+1)]
arr = list(combinations(n_arr, m))

for i in arr:
    print(i[0], end=" ")
    for j in range(1, m):
        print(i[j], end=" ")
    print()

풀이

1. 수도코드

    N, M <- input
    N_arr = 1부터 N까지 값들을 포함한 리스트
    arr = list(combinations(N_arr, M)) # nCr
       
    for i in arr:
    		print(i[0], end=" ")
    		for j in range(1, m):
    				print(i[j], end=" ")
    		print()
   

풀이:

1. N, M을 입력 받음.
2. N_arr 리스트를 선언하고, 1부터 N까지 담음 → i for i in range(1, N+1)
3. arr에 N_arr 안에서 M개의 값들을 선택하는 combinations 결과를 리스트로 저장
4. arr을 순회하며 출력
5. M개를 선택하는데, 위 출력에서 i[0]을 출력했으므로, 이제 남은건 i[1], i[2], … i[M-1]이 남음. 이를 순회

회고

• 백트래킹 문제인데 combinations로 풀어버렸다.
• combinations가 재귀로 구현되어있을거같긴 한데, 알아보고 여기에 정리하자.
• combinations를 직접 구현해보는 것도 좋을 듯 하다.