[C++]백준 - 1450번 문제

1450번: 냅색문제 (acmicpc.net)

1450번: 냅색문제

 

1450번 : 냅색문제

---

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

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

 

입력

---

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

 

 

출력

---

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

 

 

---

 

생각해 볼 점

---

벡터를 2개를 쓸 것입니다.

 

우선, 입력을 받기 전에 벡터 2개에 0을 집어넣습니다. 아무것도 안넣는 것 역시 한가지 방법이기 때문입니다.

 

입력을 2등분하여, 두 벡터에 넣습니다.

 

vector1은 0부터 2 / N까지

vector2는 2 / N부터 N까지 받습니다.

 

입력을 추가할 때마다, C를 넘지 않는 무게조합을 더하여 추가합니다.

 

예를들어, 벡터 1이 {1, 2, 4} 순서대로 입력을 받는다고 하면

 

1이 입력되기 전 : {0}

1이 입력됨 : {0, 0 + 1}

2가 입력됨 : {0, 1, 2, 1 + 2}

3이 입력됨 : {0, 1, 2, 3, 4, 1 + 4, 2+ 4, 3 + 4}

 

결과 : {0, 1, 2, 3, 4, 5, 6, 7}

 

위 벡터는 1, 2, 4의 아이템으로 만들 수 있는 모든 무게의 조합입니다.

 

벡터 2 역시 위와 동일하게 만들어 줍니다.

 

그 후, 벡터 1과 벡터 2의 아이템을 모두 조합하여 가능한 모든 경우의 수를 구할 것입니다.

 

이 때, 벡터 1과 벡터 2중 한 쪽을 정렬하면, 무게 C가 넘어가는 순간 더 비교를 하지 않아도 됩니다.

 

V2는 정렬되어있으므로 V1과 V2를 더해가던 중, C를 넘는 조합이 발견되면 break가 가능 

 

C를 넘지 않는 모든 케이스를 구하여 갯수를 출력하면 됩니다.

 

코드

---

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

int main() 
{
	int N, C;
	scanf("%d %d", &N, &C);
	
	vector<int> items1;
	vector<int> items2;
	items1.push_back(0);
	items2.push_back(0);
    
    //입력을 이등분하여 받음
	for(int i = 0; i < N / 2; i++)
	{
	    int input;
	    scanf("%d", &input);
	    
	    int s = items1.size();
        
        //새 물건이 추가될 때마다 가능한 모든 조합을 추가함
	    for(int i = 0; i < s; i++)
	    {
	        if(items1[i] + input <= C) items1.push_back(items1[i] + input);
	    }
	}
	
	//1번 경우와 동일하게 진행
	for(int i = N / 2; i < N; i++)
	{
	    int input;
	    scanf("%d", &input);
	    
	    int s = items2.size();
	    for(int i = 0; i < s; i++)
	    {
	        if(items2[i] + input <= C) items2.push_back(items2[i] + input);
	    }
	}
    
    //한쪽만 정렬
	sort(items2.begin(), items2.end());
	
	int result = 0;
	
    
    //1번 벡터와 2번 벡터의 경우의 수를 조합
	for(int item1 : items1)
	{
	    for(int item2 : items2)
	    {
        	//2번 벡터는 정렬되었으므로, 무게가 C를 넘어가는 순간 break
	        if(item1 + item2 <= C) result++;
	        else break;
	    }
	}
	printf("%d", result);
	
	return 0;
}

 

그 외

---

솔직히 어떻게 풀지 감도 못잡고 있었는데.. 검색해보니 이런 방법으로 풀 수 있을 줄은 몰랐습니다.