[Python] 백준 1182 - 부분수열의 합

https://www.acmicpc.net/problem/1182

 

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

---

풀이

비트마스킹을 배워보자.

 사실 이번 문제에서 처음 써본다.

 

ㄴㅇㄹㄴㅇ

 

태그중에 백트래킹이 있다. 원래같으면 모든 경우를 하나하나 있는지 없는지 조사하기 위해서 재귀함수 쓰고 난리부르스를 쳤을 것인데 생각하기도 싫다.

 

그래서 백트래킹 그런거 필요없는 비트마스킹을 배워본다.

비트마스킹은, 2진수 연산을 이용하여 집합의 자료구조를 매우 빠르게 연산할 수 있는(거의 O(1)) 방법이다.

다만, 집합의 크기가 좀 작을 때에만 쓸 수 있다.

뭐 외판원 문제라던가... 이번 문제라던가...

 

어쨌든 이번 문제에서는 2^N개의 경우의 수를 모두 따져주는 것이 중요하다.

여기서 아이디어는 for 문을 통해 1부터 2^N까지 돌아주면 각각의 i값들은 비트마스크로서, 이진수로 나타내면 각자 집합을 표현하고 있는 것이다!

이진수로 표현했을 때 1인 비트는 해당 수가 들어있는거고, 0인 비트는 해당 수가 포함되지 않는 것이다.

 

이 아이디어를 쓰면 다음과 같이 아주 간단하게 풀 수 있다.

 

N, S = map(int, input().split())
arr = map(int, input().split())
cnt = 0
for bitmask in range(1, 1 << N):
    total = 0
    for i in range(N):
        if bitmask & (1 << i):
            total += arr[i]
    if total == S:
        cnt += 1
print(cnt)

 

여기서 << 연산자는 비트시프트 연산으로, 1이라는 수에다가 2를 N제곱 해주는 것과 같다.

예를들어 1 << 5는 32와 같고 이진수로 나타내면 100000과 같다 (원래 1이었는데 0을 다섯 번 밀어넣어준거임)

그리고 bitmask & (1 << i) 에서 & 연산자는 and 연산으로, 해당 칸의 비트가 켜져있는지 꺼져있는지 반환해준다.

1번째꺼 &를 %로 오타냄