Algorithm/백준
[백준] 15649 n과 m 1
sunnyshiny
2023. 3. 15. 19:28
728x90
https://www.acmicpc.net/problem/15649
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
파이썬 내부 permutation을 활용한 코드
from itertools import permutations
n,m = map(int, input().split())
perm = permutations(range(1,n+1), m)
for p in perm:
print(' '.join(map(str, p)))
내부 코드가 아닌 dfs 알고리즘 코드
n, m = map(int, input().split())
back = []
visited = [False] * (n+1)
def dfs():
if len(back) == m:
print(' '.join(map(str, back)))
return
for i in range(1, n+1):
if visited[i]:
continue
back.append(i)
visited[i] = True
dfs()
visited[back.pop()] = False
dfs()
permutation을 이용하였을 때 dfs보다 메모리는 더 차지 하였지만 시간은 덜 걸렸다.
728x90