Koala - 6기/기초 알고리즘 스터디
[백준/Python] 1182번: 부분수열의 합
csharon0218
2022. 5. 19. 12:36
1182번: 부분수열의 합
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
문제 해석
비트마스크를 이용한 문제
코드
문제 풀이
문제 요구 사항을 입력받는다. 부분집합의 합을 만족하는 갯수 구하기 위한 변수를 설정한다. 비트마스크를 이용해 1부터 2^n까지 순회할 것이다. i를 이진수로 변환한다. 그 후에, 1을 곱하면 부분 집합에 속한 것이고 0을 곱하면 부분집합에 속하지 않은 것이다. 부분집합의 합이 만족하면 count 1을 증가한다.