BOJ 1182 - 부분수열의 합

N과 M 시리즈에서 사용한 논리를 적용했다. 여러 군데에서 요긴하게 잘 쓸 것 같다.

 

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

int arr[20], n, s, cnt;

void go(vector<int>& picked, int sum) {
	if (!picked.empty() && sum == s) { cnt++; }

	int next = picked.empty() ? 0 : picked.back() + 1;

	for (int i = next; i < n; i++) {
		picked.push_back(i);
		go(picked, sum + arr[i]);
		picked.pop_back();
	}
}

int main() {
	scanf("%d %d", &n, &s);

	for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
	vector<int> picked;

	go(picked, 0);
	
	printf("%d\n", cnt);

}

 

요즘 갓킹독님 블로그를 보면서 문제푸는 중인데, 갓킹독님 코드가 인상적이다.

#include <bits/stdc++.h>
using namespace std;
int n,s;
int cnt = 0;
int a[24];

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> s;
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 1; i < (1<<n); i++){ // 1<<n = 2의 n승, 공집합은 제외한다고 되어있으므로 1부터 시작
    int tmp = i;
    int tot = 0;
    for(int j = 0; j < n; j++){
      if(tmp % 2 == 1) tot += a[j];
      tmp /= 2;
    }
    if(tot == s) cnt++;
  }
  cout << cnt;
}

2중 for문으로 푸셨는데, 바깥 for문에서 부분집합의 개수 만큼 돌고, 안쪽 for문에서 2진법을 활용해서 원소들을 골라준다. ㅎㄷㄷ