시험기간이니만큼 쉬운 문제 하나 풀었다.

BOJ 1450 냅색문제
이 문제는 단순히 생각했을때 모든 물건을 넣었다 뺐다 하는 경우를 모두 고려해서 O(2^n)으로 해결할 수 있다. 하지만 그렇게 풀기에는 n=30, 너무 크다.

내가 생각한 해법은 n/2로 나눠서 모든 경우를 다 계산하고, 각 경우를 정렬해서 투포인터로 해결할 수 있다. 이 해법은 O(n + 2^(n/2))로 충분히 시간 내에 통과 가능하다.
예시를 들어보자.
n=6, c = 10, 물건의 크기를 3 4 5 4 6 2라 두었을 때를 생각하면 다음과 같다.
위 물건을 좌우로 2개로 구분한다.
3 4 5 4 6 2

왼쪽을 넣었다 뺐다를 모두 고려했을 때 물건의 무게는 다음과 같다.
0 3 4 5 7 8 9 12
오른쪽도 마찬가지로 하면 다음과 같다.
0 4 6 2 10 6 8 12

둘 다 정렬하자.
0 3 4 5 7 8 9 12 : 배열 A
0 2 4 6 6 8 10 12 : 배열 B

이제 배열 A와 B에 대해 투포인터를 사용하자. 더해서 10이 넘지 않도록 하면 된다.
A의 인덱스를 i, B의 인덱스를 j라 했을때 i는 1에서 시작하고, j는 8에서 시작해 i를 1씩 늘려 가면서 j를 내려오도록 하고, 그때의 j인덱스를 정답에 더하면 된다.
i=1 -> j=7 (0+10)
i=2 -> j=6 (3+6)
i=3 -> j=6 (4+6)
i=4 -> j=3 (5+4)
i=5 -> j=2 (7+2)
i=6 -> j=2 (8+2)
i=7 -> j=1 (9+0)
i=8 -> j=X (12+X)
여기서 7+6+6+3+2+2+1 = 27이 답이다.

이대로 정직하게 구현하면 다음과 같다.
`

include<bits/stdc++.h>

using namespace std;
typedef long long ll;
int arr[40];
vector vec1, vec2;
void dfs(int i,int e,ll S,vector& vec)
{
if(i > e) return;
vec.push_back(S + arr[i]);
dfs(i+1, e,S + arr[i], vec);
dfs(i+1, e,S, vec);
}
int main()
{
int n,c; scanf("%d %d",&n,&c);
for(int i = 1; i <= n; i++) scanf("%d", arr+i);
vec1.push_back(0); vec2.push_back(0);
dfs(1,n/2,0,vec1);
dfs(n/2+1,n,0,vec2);
sort(vec1.begin(),vec1.end());
sort(vec2.begin(),vec2.end());

//for(auto i : vec1) printf("%lld ", i);
//printf("\n");
//for(auto i : vec2) printf("%lld ", i);
//printf("\n");

int ans = 0;
auto j = vec2.end()-1;
for(auto i : vec1)
{
    while(j != vec2.begin() and i + *j > c) j--;
    if(i + *j > c) break;

    ans += (j - vec2.begin())+1;
}
printf("%d", ans);

}

`