[C++] 백준 19942 번 문제 풀이

19942번: 다이어트

 

이전부터 비트마스킹에 대해서 좀 무시하는 경향이 있었다.

때문에 비트마스킹으로 처리할 수 있는 문제도 굳이 우회해서 처리하곤 했는데,

이번 문제에서 비트마스킹의 필요성을 느껴 배워서 코딩 하였다.

 

 

 

삽질

원래 필자가 생각했던 방법은 다음과 같다.

 

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
 
using namespace std;
 
// 기준이 되는 입력
unsigned int nums;
unsigned int proteinSum = 0;
unsigned int fatSum = 0;
unsigned int carbohydrateSum = 0;
unsigned int vitaminSum = 0;
 
// 원 입력본이 들어있는 곳
vector<int> v_protein;
vector<int> v_fat;
vector<int> v_carbohydrate;
vector<int> v_vitamin;
vector<int> v_price;
 
// string 배열을 기준으로 모든 경우의 수를 탐색함
vector<string> vStr_protein;
vector<string> vStr_fat;
vector<string> vStr_carbohydrate;
vector<string> vStr_vitamin;
vector<string> vStr_price;
 
int main()
{
    ios_base::sync_with_stdio(false);
 
    unsigned int temp_protein = 0;
    unsigned int temp_fat = 0;
    unsigned int temp_carbohydrate = 0;
    unsigned int temp_vitamin = 0;
    unsigned int temp_price = 0;
 
    cin >> nums;
    cin >> proteinSum >> carbohydrateSum >> vitaminSum;
 
    // [restrict 1] : 3 <= N <= 15
    if (nums < 3 || 15 < nums)
    {
        printf("-1");
        return 0;
    }
 
    // input vector
    for (int i = 0; i < nums; ++i)
    {
        cin >> temp_protein >> temp_fat >>
            temp_carbohydrate >> temp_vitamin >> temp_price;
 
        v_protein.push_back(temp_protein);
        v_fat.push_back(temp_fat);
        v_carbohydrate.push_back(temp_carbohydrate);
        v_vitamin.push_back(temp_vitamin);
        v_price.push_back(temp_price);
    }
 
    // calculate...
}​​

 

 

30분 동안 여러가지로 생각해 봤었다.

이 문제의 제한시간은 2초고, 모든 개체의 수는 15개로 생각보다

그리 빡빡하지 않은 조건이다.

C++ 이라면 주먹구구식으로 모든 조합을 구해도 2초를 넘기지 않을 수 있을거라 생각해서

 

오리지널한 방법으로 search 방법을 찾았었다.

필자의 생각은 다음과 같았었다.

 

1) 단백질, 지방, 탄수화물, 비타민 각각 함량을 초과하는 모든 조합을 찾는다.

2) 그것을 각 vector<string> 에 밀어 넣는다.  [경우의 수이므로 set,map 은 의미가 없다]

3) 각 함량을 초과하는 모든 경우의 수를 추출한다.

4) 해당 조건들 중 [단백질, 지방, 탄수화물, 비타민] 4가지 함량을 만족시키는 경우의 수 만 다시금 추출한다.

4) 그 중에서 가격이 가장 낮은 녀석을 정답으로 출력한다.

 

문제는, 내 방법이 효율적인지? 에 대해서 의문을 품어서 거의 풀지도 못했다는 점이다.

 

비록 문제 내에서는 15개라는 제한이 있어서 끝까지 풀면 내 방법으로도 가능 하겠지만,

100개, 1000개, 10000개로 늘어났을 때의, 경우의 수를 생각하자면

내가 생각한 original 한 방법으로는 복잡도가 기하 급수적으로 늘어날 수 밖에 없을 것이다.

 

 

때문에 나는 다른 풀이들의 도움을 받고자 하였다.

 

 

 

 

도움받기

큰돌님의 블로그에서 그 해답을 찾았다.

백준 19942 다이어트 #완전탐색#비트마스킹

 

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
 
using namespace std;
 
typedef long long ll;
const int INF = 987654321;
int n, mp, mf, ms, mv;
int b, c, d, e, ret = INF, sum;
 
struct A 
{
    int mp, mf, ms, mv, cost;
}a[16];
 
map<int, vector<vector<int>>> ret_v;
 
int main() 
{
    ios_base::sync_with_stdio(false);
 
    // n을 입력 받는다.
    cin >> n;
 
    // mp, mf, ms, mv 는 각 영양성분의 기준점이 되는 녀석들이다.
    cin >> mp >> mf >> ms >> mv;
 
    // n 개수만큼 mp 에 삽입한다.
    // 이제 배열에는 n 개 만큼의 요소가 존재한다.
    for (int i = 0; i < n; i++) 
    {
        cin >> a[i].mp >> a[i].mf >> a[i].ms >> a[i].mv >> a[i].cost;
    }
 
    // for 문 선언
    // [ << ] 좌측시프트, [ >> ] 우측시프트 이므로
    // 1 << n 만큼 좌측 시프트 하라는 의미 (n 이 10 이라면 1024)
    for (int i = 1; i < (1 << n); i++) 
    {
        // 모든값 0 로 초기화
        b = c = d = e = sum = 0;
 
        vector<int> v;
 
        // < n 까지 반복
        for (int j = 0; j < n; j++) 
        {
            // 1 << j 만큼 좌측 시프트 한것을 i 와 and 연산해서 0가 아니라면,
            if (i & (1 << j)) 
            {
                // 위에서 선언한 임시백터 v 에 (j+1) 값을 push_back.
                v.push_back(j + 1);
                // 각 값들을 모두 더해 계산함.
                b += a[j].mp;
                c += a[j].mf;
                d += a[j].ms;
                e += a[j].mv;
                sum += a[j].cost;
            }
        }
 
        // 만약 모든 값들이 기준값을 초과한다면,
        if (b >= mp && c >= mf && d >= ms && e >= mv) 
        {
            // 만약 sum 값이 ret 값 미만이면. (ret = INF)
            if (ret >= sum) 
            {
                ret = sum;
                
                // map 내 인자 vector 에 vector를 push_back;
                ret_v[ret].push_back(v);
            }
        }
    }
 
    // 만약 ret 값이 INF 와 같다면 -1 출력하고 종료.
    if (ret == INF) cout << -1 << '\n';
 
    // 아니라면,
    else 
    {
        // 오름차순 정렬 
        sort(ret_v[ret].begin(), ret_v[ret].end());
        cout << ret << "\n";
 
        // ret_v[ret][0] a 출력후 종료.
        for (int a : ret_v[ret][0]) 
        {
            cout << a << " ";
        }
    }
    return 0;
}

우선 위 코드는 큰돌님의 코드를 라인별로 의미만 기재한 것이다.

 

 

 

 

해설

우선 41번째 라인인 for 문 선언부 전까지는 이해 안되는 부분이 없을것이다.

해설은 41번 라인부터 시작한다.

	// for 문 선언
	// [ << ] 좌측시프트, [ >> ] 우측시프트 이므로
	// 1 << n 만큼 좌측 시프트 하라는 의미 (n 이 10 이라면 1024)
	for (int i = 1; i < (1 << n); i++) 
	{
		// 모든값 0 로 초기화
		b = c = d = e = sum = 0;

		vector<int> v;

		// < n 까지 반복
		for (int j = 0; j < n; j++) 
		{
			// 1 << j 만큼 좌측 시프트 한것을 i 와 and 연산.
			if (i & (1 << j)) 
			{
				// 위에서 선언한 임시백터 v 에 (j+1) 값을 push_back.
				v.push_back(j + 1);
				// 각 값들을 모두 더해 계산함.
				b += a[j].mp;
				c += a[j].mf;
				d += a[j].ms;
				e += a[j].mv;
				sum += a[j].cost;
			}
		}

		// 만약 모든 값들이 기준값을 초과한다면,
		if (b >= mp && c >= mf && d >= ms && e >= mv) 
		{
			// 만약 sum 값이 ret 값 미만이면. (ret = INF)
			if (ret >= sum) 
			{
				ret = sum;
				
				// map 내 인자 vector 에 vector를 push_back;
				ret_v[ret].push_back(v);
			}
		}
	}​

 

 

 

우선 for 문의 반복형태가 다소 특이하다,

(1) < (1<<n) 까지 i 가 더해질 동안 for 돌리라는 의미인데

1 << 10 == 1024 에 해당한다.

즉 모든 경우의 수를 고려하기 위한 계산식 이다.

 

 

예를 들어 n 이 3 이라면 경우의 수는 8개 이다

000, 001, 010, 011, 100, 101, 110, 111

10 개라면 1024 개 이다.

 

위와 같이 모든 경우의 수를 따지는 이유는,

해당식에서 어떤것이 '최저가격' 을 만족하면서 '영양성분' 조건을 만족할지 모르기 때문이다.

때문에 모든 경우의 수를 고려하는것이 옳다.

 

 

 

그 후 b, c, d, e, sum 식을 모두 초기화 한 뒤 vector 를 선언한다.

 

그 후 이중 for 문에서는 n 번 반복한다, 각 개체 횟수만큼 반복 체크하기 위해서다.

 

if 문은 또 다소 특이하다. 1 << j 번 좌측 시프트하여 그 결과값과 i 를 and 연산한다.

해당 식을 사용하면, 특정 번지수에 매칭되는것만 발동된다

예시로 010 이라고 했을때, 2와 매칭되는 1<<j 일 경우 만 참이 되어 아래 식을 활성화 할 수 있다.

 

이를 자세히 살펴보면 '아름다움' 을 느낄 수 있는데,

예시로 01110 일 경우 각 0 과 1 이 번짓수에 해당한다.

0 = 1번째 재료

1 = 2번째 재료

2 = 3번째 재료 ....

즉 이와같은 비트마스크 형식으로 모든 경우의 수를 체크할 수 있는 것이다.

체크결과 해당 번지수가 1 이라면, 경우의 수 중 하나로써 타당하므로 이에 대한 계산을 진행한다.

재료는 0번이 아닌, 1번부터 진행되므로 해당 재료의 번지를 +1 하려 v 백터에 추가하고,

나머지 재료의 영양성분과 cost 를 추가한다.

 

 

 

for 문을 반복하여 b, c, d, e 를 모두 더했을때 해당 영양성분들이 기준값 이상인지를 확인한다.

맞다면 ret에 sum 을 삽입한 뒤,

rev_v[ret] 에 v 를 삽입한다.

map 형식의 int 형 key 값을 가지고 valude 는 이중백터로 선언되어 있는 형식이다.

즉,

해당 식은 ret_v 의 킷값에 [ret] == sum 값을 입력하고,

해당 sum 값의 조합으로 'v' (해당 조합식을 이루는 재료들) 을 백터형식으로 밀어 넣는다.

 

여기서 ret 의 경우, 하나도 일치하는 값이 없을경우 INF 값으로 지정된다.

때문에 만약 해당 계산식이 끝날때 까지 INF 로 유지된다면 조건에 맞는 결과가 하나도 없음을 유추할 수 있다.

 

sort 식의 경우에는, key 값은 이미 최소비용으로 정해졌으니, 해당 최소 비용값의 재료번호를 sort 하는것이다

최소비용이 정해졌는데, 뭘 sort 하는지 의아하다고 반문할 수 있으나.

문제의 예시를 보면 위와같이 겹치는 항목이 있다,

따라서 재료 갯수가 많다면, '가격이 같은데도 불구하고' 재료가 서로 다른 것이 있을 가능성이 있다.

위 문제에서 사전순으로 가장 빠른 것을 출력한다고 명시 하였으니, sort 한 후 [0] 번을 출력하는것이 옳다.

 

그 후에는 ret 을 출력하는데, ret이 항상 최소비용일 수 있는 이유는 위에서 

해당 식을 사용했기 때문이다. 

그 후 마지막으로 ret_v[ret][0] 를 공백으로 구분하여 출력한다.

 

 

나의 잘못

언제나 알고리즘 문제를 풀 때 느끼는건데

나는 문제를 푸는데 과도하게 해석하는 측면이 있다.

해당 문제의 키 포인트는

각 재료들은 번호에 따라 묶여있단 점이다.

 

때문에 굳이 나처럼 단백질만 따로, 지방만 따로, 탄수화물만 따로, 비타민만 따로

계산한 뒤 이를 다시 추려서 가격을 추론할 필요가 없다.

불필요한 계산과정이 낭비된다.

 

이 문제는 굳이 비트마스킹을 사용하지 않아도 그럭저럭 풀만한 문제이다.

 

하지만 내가 생각한 방법은

굉장히 멍청한 방법이고,

문제를 제대로 읽지 않았다는 반증이다.

 

 

 

결론

근래들어 사실 C++ 문법 자체는 크게 익숙해 져서 어려움이 없었다.

물론 아직 dllExport, define mecro 등에 대해서는 잘 모르는것이 사실이나,

잘 쓰는 문법들도 아니고 그때 그때 찾아보면 되기 때문이다.

 

하지만 이 문제를 풀면서 언어 문법 외에

알고리즘 적으로 생각의 지평을 넓혀야 한다는 느낌을 강하게 받았다.

 

끝