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

문제링크

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

15651번: N과 M (3)

문제설명

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

'같은 수를 여러 번 골라도 된다' 는 조건이 추가되었다. 이 조건으로 인해 해당 문제는 백트래킹으로 풀이하면 pruning 과정이 따로 필요없이 dfs로 경우의 수를 탐색해주면 된다.

또한, 경우의 수로 풀이하는 경우에는 중복순열을 이용해서 풀 수 있다.

 

문제풀이

1. 중복 순열

순서가 달라지면 다른 수열로 인정하며, 같은 수를 여러 번 골라도 된다는 조건이 있으므로 중복 순열임을 알 수 있다.

itertools의 product 를 활용하여 풀었다. 시간은 백트래킹 알고리즘으로 채점했을 때보다 덜 소요되었다.

import sys
from itertools import product

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

 

2. 백트래킹

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

중복도 허용하고, 순서가 달라지면 다른 수열로 인정하기 때문에 숫자의 중복이나, 순서의 중복에 대한 pruning 작업은 따로 필요없다.

M만큼의 길이의 수열마다 출력을 해야하므로 탈출 조건은 스택의 길이가 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):
        ret.append(i)
        dfs()
        ret.pop()
dfs()