C++ / 백준 / 14225 / 부분수열의 합

문제

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

14225번: 부분수열의 합

 

문제풀이

비트 마스크를 이용하여 풀었다.

숫자가 1, 2, 3을 입력받았을 경우,

1, 2, 3, 1+2, 1+3, 2+3, 1+2+3의 7가지 경우가 있다.

1부터 7까지의 이진수를 표현하고, 0인 부분은 더하지 않고 1인 부분만 더하게 되면 부분 수열의 합을 모두 구할 수 있다.

자연수는 1부터 이므로 i=1부터, 1<<3까지면 1~7까지 반복을 하게 되고,

j는 자릿수만큼 반복을 하면서 001, 010, 100의 3자리를 i와 비교하면서 1인 부분만 sum에 저장한다.

배열은 왼쪽부터 오른쪽으로 갈수록 칸이 커지므로 숫자들을 오름차순으로 정렬 먼저 하였다.

정렬을 했으므로 첫 수가 1이 아니면 1은 더 이상 나올 수 없으므로 1이 정답이 된다.

seq_num은 0으로 시작하고 sum의 값이 seq_num+1일 때만 값을 바꿔준다.

정렬에 같은 숫자가 있으면 sum이 seq_num과 같거나 작은 수가 나올 수 있지만, sum이 seq_num보다 큰 수가 나온다면 이후에 나올 큰 값 중 제일 작은 값이 sum이 된다. 

1 2 2 7에서 1+2+2에서 7로 넘어가는 부분이 그 경우에 해당된다.

따라서 sum은 seq_num이하의 수가 나오면 넘기고 sum+1의 값이 나오면 seq_num에 저장하고, sum+2 이상의 값이 나오면 seq_num +1을 하여 출력한다.

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int N = 0;
	int i = 0, j = 0;
	int sum = 0;
	cin >> N;
	vector<int>seq(N, 0);
	int seq_sum;
	for (i = 0; i < N; ++i) {
		cin >> seq[i];
	}

	sort(seq.begin(), seq.end());
	seq_sum = 0;
	for (i = 1; i < (1 << N); ++i) {
		sum = 0;
		for (j = 0; j < N; ++j) {
			if (i & (1 << j)) sum += seq[j];
		}
		if (seq_sum + 1 < sum) {
			cout << seq_sum + 1;
			return 0;
		}
		else if (seq_sum + 1 == sum)seq_sum = sum;
	}

	cout << seq_sum + 1;
}