[BOJ:1450] 냅색문제

문제

www.acmicpc.net/problem/1450

1450번: 냅색문제

 

코드

//https://www.acmicpc.net/problem/1450
#include<cstdio>
#include<algorithm>
using namespace std;

#define mxl 30
#define mxn 30
int sum1[mxl], sum2[mxl], l1, l2, a[mxn];

void dfs(int start, int end, int sum, int flag, int m) {
    if (sum > m) return;
    if (start == end) {
        if (flag == 1) sum1[l1++] = sum;
        else sum2[l2++] = sum;
        return;
    }
    dfs(start + 1, end, sum, flag, m);
    dfs(start + 1, end, sum + a[start], flag, m);
}
int main() {
    freopen("input.txt", "rt", stdin);
    int n, m, cnt = 0;
    scanf("%d%d", &n, &m);

    for (int i = 0; i < n / 2; i++) scanf("%d", &a[i]);
    dfs(0, n / 2, 0, 1, m);
    sort(sum1, sum1 + l1);

    for (int i = n / 2; i < n; i++) scanf("%d", &a[i - (n / 2)]);
    dfs(0, n - (n / 2), 0, 2, m);
    sort(sum2, sum2 + l2);

    for (int i = 0, j = l2 - 1; i < l1 && j >= 0; i++) {
        while (sum1[i] + sum2[j] > m) j--;
        cnt += j + 1;
    }
    printf("%d", cnt);
    return 0;
}

문제해결방법

• 주어진 물건을 반반 씩 입력 받아서 부분집합을 구하는 방식으로 각 물건을 선택하여 합을 구한다.
• 이때 구해진 합들은 부분집합의 원소들의 (선택된 물건들의) 총합을 나타낸다.
• 두 개의 합 배열들을 정렬하고 투포인터 알고리즘으로 해결한다.
• for 문에서 i를 0인덱스를 기준으로 j는 마지막 인덱스부터 sum1[i] + sum[j] > m 인 조건이 나타나면 j를 하나 감소시켜나가면서 처음으로 m과 같거나 작은 j의 값에서 +1을 해서 카운트값을 증가시킨다. 여기서 j+1을 하는 이유는 인덱스를 0부터 했기 때문이다.