Be a developer

앞서 풀어본 1182번 문제를 비트마스크를 이용해 푼다. 명심해야 할 핵심은 부분집합을 '하나의 수'로 나타낸다는 개념이다. {1, 3, 5}를 101010 로 나타내어 42라는 하나의 수로 나타내는 것이다.(2^1 + 2^3 + 2^5 = 42) 집합의 원소 값을 이진수의 자리수로 생각하는 것이다. 즉, 42 = {1, 3, 5} 이다. 해당 문제에서는 집합을 '하나의 수'로 보는 같은 개념을 사용하지만 원소 값 자체를 인덱스로 사용하진 않는다. n이 주어지면 집합에 있는 원소의 개수는 n개가 된다. 이는 '하나의 수'로 치환될 수 있는데, n자리 수의 이진수로 표현할 수 있다. 따라서 모든 부분 집합은 0~(1

sum은 인자로 전달해준다. 중간에 원소 몇 개로 합을 완성할 수도 있지만, 아래 코드에서 sum과 s가 같더라도 이후의 원소가 들어오는 것에 따라서 다시 sum과 s가 같아질 수 있다. 따라서 경우의 수를 (s==sum && i == n)과 (s != sum && i == n) 두 가지로 나누어서 풀어야 한다. 또한 합이 0이 입력되면, 아무것도 선택하지 않아도 0이 되므로, 공집합은 허용되지 않는다. 따라서 답을 출력할 때 1을 빼준다. 123456789101112131415161718192021222324252627282930#include #include #include using namespace std; int n, s;vector v(20);int ans; void go(int i, int ..