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

28 Apr 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 1450 : 냅색문제(링크)

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

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

입력

첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 $10^9$보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 $10^9$보다 작거나 같은 자연수이다.

출력

첫째 줄에 가방에 넣는 방법의 수를 출력한다.

알고리즘

1. Meet in the middle

풀이

• 완전탐색으로 풀기에는 시간초과
• DP로 풀기에는 상태값 저장이 힘듬 10억개 공간복잡도 초과
• Meet in the middle
  • 범위를 두개로 쪼개서 결과값을 탐색해가는 알고리즘
  • n을 n/2 * 2 기반으로 탐색

코드

// BOJ - 1450 : 냅색문제
#include <bits/stdc++.h>
using namespace std;

int n, c, a[34], res;
vector<int> v, v2;

void go(int here, int _n, vector<int>& v, int sum)
{
	if (sum > c) return;
	if (here > _n)
	{
		v.push_back(sum);
		return;
	}
	go(here + 1, _n, v, sum + a[here]); 
	go(here + 1, _n, v, sum);
	return;
}

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

	cin >> n >> c;

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

	go(0, n / 2 - 1, v, 0);
	go(n / 2, n - 1, v2, 0);
	sort(v.begin(), v.end());
	sort(v2.begin(), v2.end());

	for (int b : v)
	{
		if (c - b >= 0)
		{
			res += ((int)(upper_bound(v2.begin(), v2.end(), c - b) - v2.begin()));
		}
	}
	cout << res << '\n';
	return 0;
}

평가

• vector 2개를 활용해 n을 n/2 두개로 쪼갠 후 경우의 수 탐색
• upper_bound를 활용해 정렬된 배열의 인덱스 개수 수월하게 찾을 수 있음