Carpe Diem Carpe Diem

n,m=map(int,input().split()) nlist=list(map(int,input().split())) nlist.sort() answer=[] def dfs(depth,n,m): if len(answer)==m: print(*answer) return x=0 for i in range(depth,n): if x!=nlist[i]: # x가 list의 숫자와 같지 않다면(중복되는 수열 여러번 출력x) answer.append(nlist[i]) dfs(i,n,m) #비내림차순 x=nlist[i] answer.pop() dfs(0,n,m)

1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. n,m=map(int,input().split()) answer=[] def dfs(depth,n,m): if len(answer)==m: print(*answer) return for i in range(depth,n+1): answer.append(i) dfs(i,n,m) answer.pop() dfs(1,n,m)

(2)와 다른 점은 n개의 수를 담은 list가 주어졌다는 것이고, 중복이 허용된다는 것이다. 따라서 dfs(i+1,n,m)이 아니라 dfs(i,n,m)을 해주어야한다. n,m=map(int,input().split()) nlist=list(map(int,input().split())) nlist.sort() answer=[] def dfs(depth,n,m): if len(answer)==m: print(*answer) return for i in range(depth,n): answer.append(nlist[i]) dfs(i,n,m) answer.pop() dfs(0,n,m)

(1)과 다른 점은 오름차순으로 나열된다는 것이다. 따라서 answer에 숫자가 이미 있는지 없는지 확인해보는 코드를 추가해야한다. n,m=map(int,input().split()) visited=[False]*(n+1) answer=[] def dfs(depth,n,m): if len(answer)==m: print(*answer) return for i in range(depth,n+1): if i not in answer: answer.append(i) dfs(i+1,n,m) answer.pop() dfs(1,n,m)

백트래킹의 기본원리를 알 수 있다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 1. visited 리스트 만들기 (중복방지) 2. depth, n, m을 입력받는데 이때, depth는 answer의 길이. 3. depth가 m과 같아진다면 함수가 종료된다. 4. depth와 m이 같지 않다면 아직 탐색해야 할 숫자가 남았다는 의미이므로 visited에 False값이 저장되어 아직 방문하지 않은 숫자를 방문한다. 4-1. 방문한 숫자는 방문했다는 의미로 visited에 True를 저장해주고 depth를 1증가시킨 상태에서 재귀함수를 실행한다. 5. 함수를 다시 실행하면 금방 방문한 숫자를 answer배열에 저장하고 해당 함수에서 나오게 되면 방문했다는 표시를 다시 False로 바꿔주고 해당 ..