[Algorithm] 1일1솔 - 백준 15650 N과 M (2) (python3)

문제링크

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

15650번: N과 M (2)

 

문제설명

앞서 풀이했던 15649번: N과 M(1) 문제와 유사하며, 문제의 조건이 약간 변형되었다.

'고른 수열은 오름차순이어야 한다' 는 조건이 추가되었다. 백트래킹으로 풀이하면 pruning 과정에서 해당 조건을 추가해주면 된다.

또한, 경우의 수로 풀이하는 경우에는 오름차순 조건을 충족시킨다는 건 순서 상관없이 같은 수열로 취급한다는 의미이므로, 조합을 이용해서 풀 수 있다.

 

문제풀이

1. 조합

이 문제에서는 수열을 오름차순으로 정렬하여 출력해야 한다는 조건이 있으므로, 순서 상관없이 같은 수열로 취급하고 있음을 알 수 있다. itertools의 combinations 활용하여 풀었다. 시간은 백트래킹 알고리즘으로 채점했을 때보다 덜 소요되었다.

import sys
from itertools import combinations

n,m = map(int, sys.stdin.readline().split())
comb = combinations(range(1,n+1), m)
for x in comb:
    print(*x)

 

2. 백트래킹

'고른 수열은 오름차순이어야 한다' 는 새로운 조건 을 충족시키기 위해 가지치기 작업을 약간 변형해주었다.

stack이 비어있거나, stack이 비어있지 않으면서 stack의 마지막 요소보다 새로 추가할 자연수 i가 클 때 자연수 i를 추가해주었다.

수를 추가해준 후, 탐색 작업(dfs)이 끝난 후에는 다시 stack에서 제거(pop) 하는 작업을 반복 수행하였다.

M만큼의 길이의 수열마다 출력을 해야하므로 탈출 조건은 스택의 길이가 M이 될 때로 설정했다.

import sys

n,m = map(int, sys.stdin.readline().split())
ret = []	# stack
def dfs():
    if len(ret) == m:	# 탈출 조건(ret 길이가 m 되면 출력)
        print(*ret)
        return
    for i in range(1,n+1):
        if not ret or (ret and i > ret[-1]):  # 가지치기(pruning)
            ret.append(i)
            dfs()
            ret.pop()
dfs()