개구리의 개발 블로그 개구리의 개발 블로그

백준 1182번 부분수열의 합 파이썬 문제 링크 - https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분수열은 연속할 필요 없이 주어진 수열에서 원소를 중복 없이 선택하면 된다. 즉, 주어진 수열의 순서가 바뀌어도 똑같은 답을 갖게 된다. 처음에는 백트래킹으로 시도했다. 전체 수열에서 원소를 선택하는 경우와 선택하지 않는 경우를 나누어 탐색한다. 하지만 DFS 도중에 가지치기 되는 경우가 없기 때문에 사실상 ..