Search

BOJ 1182 부분 수열의 합

URL
태그
브루트포스 알고리즘
백트래킹
www.acmicpc.net
https://www.acmicpc.net/problem/1182

문제 설명

•
크기가 NN인 배열의 부분 수열 중에서 합이 S가 되는 경우의 수를 구하는 문제

예제 입력/출력

•
입력1
5 0 -7 -3 -2 5 8
Plain Text
복사
•
출력1
1
Plain Text
복사

제약 조건

•
1≤N≤201 ≤ N ≤ 20
•
∣S∣≤1,000,000|S| ≤ 1,000,000

문제 풀이

•
부분수열과 조합 알고리즘의 관계
◦
nC1 + nC2 + nC3 + ⋯ + nCn=2n−1_nC_1 \ +\ _nC_2 \ + \ _nC_3 \ + \ \cdots \ + \ _nC_n = 2 ^n - 1
◦
크기가 nn인 수열의 부분수열의 개수는 2n−12^n - 1
▪
각 원소에 대해 선택함과 선택 안함 두 가지 경우가 존재함.
▪
따라서, 각 원소의 상태가 2가지 가능하고, 원소의 개수가 nn이므로 2n2^n개가 나옴.
▪
여기서, 전부 다 선택 안 하는 경우 한 가지를 빼야 하므로 2n−12^n - 1개가 나옴.
비교 코드
•
부분수열 알고리즘을 직접 구현
◦
풀이1 - O(2N)O(2^N)
•
조합 알고리즘을 이용하여 부분수열 알고리즘을 구현
◦
풀이2 - O(2N)O(2^N)

시간 복잡도 계산

•
최악의 경우 O(220)O(2^{20})
◦
약 1,048,576회 연산 필요

풀이 코드

풀이1
풀이2