[BOJ/백준] 1450 C++ 냅색문제

오늘의 포스팅은 1450 냅색문제 입니다! 

solved에서 제공하는 난이도 기준 골드 1에 위치하고 있습니다!

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

1450번: 냅색문제

 

 이번 문제도 저번의 포스팅처럼 중간에서 만나기 라는 개념을 또 사용합니다!

이번 문제는 저번에 풀었던 것보다 조금은 더 이해하기 힘들게 응용하기 때문에, 저번 포스팅을 보지 않으셨거나 중간에서 만나기라는 개념을 처음 접해 보셨다면 아래의 링크로 한 번 확인하고 오시는 것을 추천드립니다!!

https://haepalea.tistory.com/4

[BOJ/백준] 7453 C++ 합이 0인 네 정수

 

 일단 이 문제를 해석하자면, 어떠한 최대 가용 무게가 C인 가방 하나가 주어집니다.

이 때, N개의 물건을 여러개 무작위로 선택$($중복 없이$)$하고, 이 무게가 C이하라면 정답을 저장하는 ans라는 변수에 1을 더해줍니다!

 

 문제 자체가 이해하기에 어렵다거나 난해하진 않으니 바로 어떻게 풀어야 할 지 가닥을 잡아볼까요?

일단, 본격적으로 들어가기 전에 중간에서 만나기 없이 그냥 브루트포스 방식으로 부딪혀 보면 어떻게 될까요?? 이는 아마  O$($(2^N)$)$이라는 시간 복잡도가 발생합니다..! 그 이유는 N개의 물건은 가방 C에 들어갈 지 혹은 들어가지 않을 지 2가지의 경우를 가지게 되기 때문이죠! 그렇기 때문에 그냥 머리를 박는 브루트포스 방식으로는 연산의 수가 대략 2^N번이 발생합니다!

그렇다면, 문제에서 주어지길 N은 30까지 입력이 가능하니 2^30 -> 약 10억번의 연산 수이므로, 1억번 당 1초의 시간이 소요된다고 했을 때 터무니 없이 큰 시간이 걸림을 알 수 있으니, 단순 브루트 포스로는 풀 수 없겠다는 생각이 듭니다!

 

 자 이제 중간에서 만나기 개념을 적용해서 풀어볼까요?

일단, N개의 물건을 A그룹$($0번 인덱스부터 (N-1)/2인덱스까지$)$과 B그룹$($N/2번 인덱스부터 N-1인덱스까지$)$으로 나눕니다! 그리고, A그룹은 냅두고 B그룹을 set_Sum이라는 재귀 함수를 사용하여 모든 경우를 sum이라는 새로운 배열에 저장합니다!

그림으로 예를 들면!

 

자 느낌이 오시나요 ? 이걸 코드로 확인하면!

 이렇게 됩니다! 함수가 시작할 때 d의 초기 값을 N/2로 준다면, d가 N-1까지 재귀를 돌고 sum 벡터에 지금까지 더해 온 tmp 값을 추가 해주는 식으로 함수를 구현합니다!

 

 그러면 이제 A 그룹을 비슷한 재귀함수를 사용해서, 재귀의 깊이$($재귀 횟수$)$가 N/2가 되면, 지금까지 더해온 값을 cmp라고 할 때, sum 배열에서 C-cmp$($C는 초기에 주어진 가방의 최대 가용 무게$)$보다 작거나 같은 요소가 몇 개가 있는 지 알아보고 나중에 출력할 ans라는 변수에 개수를 더해주면 됩니다!

코드로 확인해보면!

 이런 식으로 구현하게 됩니다!

여기서 포인트는 sum배열은 set_Sum 함수가 끝나고 정렬을 해준 후, 이진탐색인 upper_bound를 통해 C-cmp보다 작거나 같은 요소들의 개수를 구하는 것과 cmp+v[d]가 C보다 크면, 조건에 만족하지 않으므로 무시하는 것이 있습니다! 깔끔하죠!?

앗 참, set_Sum, Func 함수 내에 C보다 큰 무게에 대해 무시하는 조건을 달지 않으면 자료형 쪽에서 오버플로우가 발생할 수 있습니다!

그렇기 때문에 저와 다르게 if문으로 적절히 처리하기 귀찮으시다면 long long 자료형을 사용하세요! 통과는 문제 없이 되는 것 같습니다!

 

 자 이제 전체 코드를 보여드리고 이만 물러나겠습니다!

질문 혹은 오류 및 오타가 있다면 댓글로 알려주세요!!!

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define LL long long

int N,C;
vector<LL> v, sum;
LL ans{0};

void Func(int d, LL cmp){
    if(d>=N/2){
        int idx = upper_bound(sum.begin(),sum.end(),C-cmp)-sum.begin();
        ans+=idx;
        return;
    }
    Func(d+1,cmp);
    if(cmp+v[d]<=C){
        Func(d+1,cmp+v[d]);
    }
}

void set_Sum(int d, LL tmp){
    if(d>=N){
        sum.push_back(tmp);
        return;
    }
    set_Sum(d+1,tmp);
    if(tmp+v[d]<=C){
        set_Sum(d+1,tmp+v[d]);
    }
}

void Solve(){
    set_Sum(N/2,0);
    sort(sum.begin(),sum.end());
    Func(0,0);
    cout<<ans<<'\n';
}

void Init(){
    cin>>N>>C;
    v.resize(N);
    for(int i=0; i<N; i++){
        cin>>v[i];
    }
}

int main(){
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    Init();
    Solve();
    return 0;
}