[ 백준 1450] 냅색문제(C++)

 

1450번: 냅색문제

문제!

---

세준이는 N개의 물건을 가지고 있고, 최대 C만큼의 무게를 넣을 수 있는 가방을 하나 가지고 있다.

N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하시오.

 

---

 

문제는 짧고 간결한 문제....

 

 

문제를 풀기전에 투포인터를 사용하는 문제라는걸 알고 풀어서 단순히 풀 수 있을줄 알았지만

 

일반탐색 시 2의 30승..

 

누적합... 탐색 방법을 다 생각해보고 코드도 작성해 보았지만 

이 방법으로도 실행시간을 크게 줄일수도 없었습니다.

 

 

 

 

그렇게 막막 찾아보고 풀다보니

이때까지 풀어왔던 투포인터의 문제들과는 다른 방식의 투포인터인것을 알았습니다.

 

약간 투포인터보다는 분할 탐색? 같은 느낌이였습니다.

 

 

 

 

 

 

그럼 시작!

---

먼저 

 

평범한 입력

cin >> n >> c;

	v.resize(n, 0);

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

 

그다음

 

 

벡터 2개를 선언해주고

	vector <long long> P1;
	vector <long long> P2;
    
    dfs(0, n / 2 - 1, P1, 0);
	dfs(n / 2, n - 1, P2, 0);

 

 

dfs를 통해 선택한경우와 선택안할 경우를 모두 고려해줍시다

void dfs(int start, int end, vector <long long>& part, long long sum) {
	if (start > end) {
		part.push_back(sum);
		return;
	}
	else {
		dfs(start + 1, end, part, sum);
		dfs(start + 1, end, part, sum + v[start]);
	}
}

 

그렇게 두 부분으로 나누어진 모든 경우의수? 가 생성됩니다.

 

 

이제 P1의 원소를 하나씩 선택하고 될수있는 값들을 P2에서 찾아서 갯수를 구해줍시다.

sort(P2.begin(), P2.end());

	int cnt = 0;


	for (int i = 0; i < P1.size(); i++) {
		long long x = c - P1[i];
		cnt += upper_bound(P2.begin(), P2.end(), x) - P2.begin();// 위치 찾기
	}

 

 

 

여기서 조건에 맞는 수를 찾기위해 이분탐색을 합니다.

 

 

**이분탐색 함수

upper_bound

조건에 맞는 수의 마지막 등장하는 위치를 반환  해주는 함수입니다! 

 

 

비슷한 함수로는

lower_bound

가 있는데 이 경우는 조건에 맞는 수가 처음 등장하는 위치를 반환해줍니다. ***

 

 

이렇게 반을 나눠 생각하고 조건에 맞춰 걸러주니 훨씬 빠른 실행시간을 보장받을수 있었습니다!

 

 

여기가 끝!

 

 

 

 

ALL

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector <long long>  v;


void dfs(int start, int end, vector <long long>& part, long long sum) {
	if (start > end) {
		part.push_back(sum);
		return;
	}
	else {
		dfs(start + 1, end, part, sum);
		dfs(start + 1, end, part, sum + v[start]);
	}
}

int main() {
	int n, c; 
	vector <long long> P1;
	vector <long long> P2;

	cin >> n >> c;

	v.resize(n, 0);

	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	dfs(0, n / 2 - 1, P1, 0);
	dfs(n / 2, n - 1, P2, 0);

	sort(P2.begin(), P2.end());

	int cnt = 0;


	for (int i = 0; i < P1.size(); i++) {
		long long x = c - P1[i];
		cnt += upper_bound(P2.begin(), P2.end(), x) - P2.begin();// 위치 찾기
	}



	cout << cnt;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!