[C++] 1450번 냅색문제 - 이분 탐색, 중간에서 만나기

1. 문제

• N개의 물건과, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다. N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

<입력>

• - 1 -   $N,C(1\le N\le 30,0\le C\le {10}^9$
• - 2 -   $w(1\le w\le {10}^9)$

<출력>

• 가방에 넣는 방법의 수

2. 재정의

• C이하의 부분 수열의 합의 개수

3. 해결방법

1. 수열의 반으로 쪼갠 후 부분 수열의 합을 모두 구한다. 그리고 이를 v1, v2에 저장한다
2. v2를 탐색하면서 C - v2의 값보다 작거나 같은 v1의 원소의 수만큼 cnt를 더하고 이를 출력한다.

4. 실수한 점, 개선할 점

• ${10}^9\times 30$은 int형 범위를 넘어갈 수 있다.
• lower_bound와 upper_bound를 잘 사용하자. lower_bound는 같거나 큰 첫 원소, upper_bound는 초과하는 첫 원소의 주소를 반환하며 .begin()을 빼면 index가 나오고 발견하지 못하면 .end()가 나오며 이는 범위를 벗어난다. 실제 개수는 index+1을 하면 되므로 upper_bound만큼 그냥 더해주면 된다.
• lower_bound가지고 장난치다가 혼났다.... 중간에서 만나기... 내 머리카락을 주고 익힌 것 같다. 찌발...

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;

const int MAX_N = 31;

// <문제>
// 물건의 개수 N, 최대 무게의 크기 C
ll N, C;
// 물건의 무게 w[]
ll w[MAX_N];

// 절반 부분 수열의 합 v1, v2
vector<ll> v1, v2;
// 가방에 넣는 방법의 수
ll cnt;

void input() {
    cin >> N >> C;
    for(int i=0; i<N; i++)
        cin >> w[i];
}

void brf(int s, int e, ll sum, vector<ll>& v) {
    // 절반만 떼서 부분 수열의 합 구하기
    if(s == e) {
        if(sum <= C)
            v.push_back(sum);
        return;
    }
    
    brf(s+1, e, sum, v);
    brf(s+1, e, sum + w[s], v);
}

void solve() {
    brf(0, N/2, 0, v1);
    brf(N/2, N, 0, v2);
    // 이분탐색을 하기 위해 v를 오름차순 정렬하기
    sort(v1.begin(), v1.end());
    
    for(int i=0; i<v2.size(); i++)
        cnt += upper_bound(v1.begin(), v1.end(), C - v2[i]) - v1.begin();
}

int main() {
    fastio;
    
    input();
    
    solve();

    cout << cnt;
    
    return 0;
}

 

<lower_bound(), upper_bound() 함수>

https://blockdmask.tistory.com/168

[탐색] lower_bound, upper_bound

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.