[Algorithm] 1일1솔 - 백준 15652 N과 M (4) (python3)

문제링크

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

15652번: N과 M (4)

 

문제설명

앞서 풀이했던 N과 M 시리즈 문제(위 링크 참고)와 유사하다.

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

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

[Algorithm] 1일1솔 - 백준 15651 N과 M (3) (python3)

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

또한, 경우의 수로 풀이하는 경우에는 비내림차순 조건을 충족시킨다는 건 순서 상관없이 같은 수열로 취급하며, 같은 수도 중복하여 인정한다는 의미이므로, 중복조합을 이용해서 풀 수 있다.

 

 

문제풀이

1. 중복조합

중복조합 nHr을 구하기 위해서 itertools 의 combinations_with_replacement 를 사용해서 풀이하였다.

import sys
from itertools import combinations_with_replacement

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

2. 백트래킹

stack이 비어있는 경우 또는, stack에 수가 들어있는 경우 순서 조건(비내림차순) 고려하여 if문에서 pruning 작업을 수행했다.

자연수 i 추가한 후 dfs로 탐색하고, 이후 스택에서 자연수 pop하여 제거하며 반복탐색한다.

탈출 조건은 스택의 길이가 M이 될 때로 설정하였다.

import sys

n, m = map(int, sys.stdin.readline().split())
ret = []
def dfs():
    if len(ret) == m:
        print(*ret)
        return
    for i in range(1, n+1):
        if not ret or (ret and ret[-1] <= i):
            ret.append(i)
            dfs()
            ret.pop()
        else:
            continue
dfs()