알고리즘 공부(C++)
백준 15650 N과 M(2) - 백트래킹문제
혀니리리
2022. 8. 28. 13:44
728x90
15650번: N과 M (2) (acmicpc.net)
15650번: N과 M (2)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
N과 M문제와 매우 비슷 but 오름차순만 정렬해야된다는 것이 달랐음.
N,M = map(int, input().split())
lst = []
visited = [False] * N
def dfs(depth):
if depth == M:
print(' '.join(map(str, lst)))
return
for i in range(N):
if not visited[i]:
for j in range(i+1):
visited[j] = True
lst.append(i + 1)
dfs(depth + 1)
for j in range(i+1):
visited[j] = False
lst.pop()
dfs(0)
나의 아이디어: 기존것을 다 True로 만들면... 더이상 그쪽은 가지 않으니까 오름차순 정렬할것이다.
결과: 맞긴 함.. 그런데 뭔가 더 효율적인 방법이 있을듯
n,m = list(map(int,input().split()))
s = []
def dfs(start):
if len(s)==m:
print(' '.join(map(str,s)))
return
for i in range(start,n+1):
if i not in s:
s.append(i)
dfs(i+1)
s.pop()
dfs(1)
결론은 요렇게! 원래는 매 반복문마다 for i in range(N+1) 요랬다면 이번엔 걍 지금의 depth부터 참조를 시작하면 알아서 거기부터 판단하기 시작함.
그러므로 for i in range(start, n+1)이런식으로 됨
간단하네... 새로운걸알았다.
역시 백트래킹 같은 알고리즘은 걍 하면 할수록 깨닫는군.....
아직은 진짜 기본문제지만 점차 익혀가자
728x90