[백준 1450] 냅색 문제

백준 1450번 : 냅색 문제

www.acmicpc.net/problem/1450

1450번: 냅색문제

---

/* 문제 설명 */

N개의 물건과 최대 C만큼의 무게를 넣을 수 있는 가방이 있을 때

가방에 물건을 넣을 수 있는 방법의 수를 구하시오. (N은 30보다 작거나 같은 자연수)

 

/* 해결 방안 */

풀이로 완전탐색이 떠오르지만, N=30인 경우 2^30이 되어 시간초과가 난다.

그렇다면, 2^30을 줄이려면 어떻게 해야할까?

→ 문제를 절반으로 나누어 생각한다. (Meet In The Middle)

 

*Meet In The Middle

N이 클 때, 절반으로 쪼개서 탐색하는 방법으로

2^n시간은 어렵지만 2^(n/2)은 가능할 때, 고려해볼 법 하다.

 

자세한 설명은 아래 링크 참조

blog.naver.com/kks227/221382873753

밋 인 더 미들(Meet in the Middle) (수정: 2018-10-25)

blog.naver.com/chogahui05/221374387858

meet in the middle 알고리즘 - 반으로 쪼갠다.

 

/* 구현 과정 */

1. 주어진 N 크기의 배열을 반(N/2)으로 나눈다.

2. 왼쪽에서 만들어지는 모든 경우(L)와, 오른쪽에서 만들어지는 모든 경우(R)를 구한다.

3. 각각의 범위에서만 만들어지는 경우를 더해준다. ans = L.size() + R.size();

4. L을 for문으로 돌면서, 이분 탐색(upper bound)을 통해  R에서 C-L[i] 값이 몇 번째(pos)에 있는지 알아낸다.

5. R[pos]까지는 가방에 넣을 수 있는 경우이기 때문에 ans += pos; 를 해준다.

6. 아무것도 넣지 않는 경우가 있으므로 마지막에 ans+=1; 해준다.

 

/* 소스 코드 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, c, arr[35], ans;
vector<ll>l, r;

//st와 en까지 가능한 경우의 합을 찾는다.
void dfs(ll st, ll en, ll sum, vector<ll> &v) {
	if (sum > c) return;
    //끝까지 다 돌은 경우
	if (st == en) {
		if(sum != 0) v.push_back(sum);
		return;
	}
    //이번 꺼, 포함 안하는 경우
	dfs(st + 1, en, sum, v);
    //이번 꺼, 포함 
	dfs(st + 1, en, sum + arr[st], v);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n >> c;
	for (int i = 0; i < n; i++) cin >> arr[i];

	dfs(0, n / 2, 0, l);
	dfs(n / 2, n, 0, r);

	ans = (ll)l.size() + (ll)r.size();
	sort(r.begin(), r.end());

	//이분탐색
	for (int i = 0; i < l.size(); i++)
	{
		ll x = c - l[i];
		ll pos = upper_bound(r.begin(), r.end(), x) - r.begin();
		ans += pos;
	}
    
    //아무것도 포함되지 않는 경우도 +1 해준다
	cout << ans + 1;
}

/* 얻어갈 점 */

1. N이 큰 경우에는 밋 인더 미들을 떠올려보자.

2. 반복문 대신 dfs(st+1) 처럼, 인자로 탐색을 하자.

3. 매개변수로 vector를 넘길 때, &를 넣어주는 걸 까먹지 말자.

4. upper_bound는 x값 보다 한 칸 큰 값을 반환한다.

 

 

 

 

---