[백준/C++] 2961번: 도영이가 만든 맛있는 음식(S2)

 

문제

https://www.acmicpc.net/problem/2961

2961번: 도영이가 만든 맛있는 음식

 

사용한 알고리즘

• 비트마스킹

Bitwise 연산자를 코드에서 써본 건 처음이다.
왜냐면 어제 처음 배웠기 때문! ㅎ

 

 

풀이

도영이가 가지고있는 N개의 재료에 대해 모든 조합(총 2^N-1가지)을 살펴봐야 한다.
비트마스킹으로 조합을 생성해보자.

재료가 총 4개 있다고 해보자.
0001 (0번 재료 선택)
0010 (1번 재료 선택)
...
1111 (0,1,2,3번 재료 선택)
이렇게 2진수로 나타낼 수 있다.

그리고 bitwise AND 연산(&)은
두 비트가 모두 1일때는 1, 그렇지않으면 0을 리턴한다.

 

0101인 경우를 예시로 살펴보자.

0101 & 0001 == 0001
0101 & 0010 == 0000
0101 & 0100 == 0100
0101 & 1000 == 0000

따라서 0101인 경우, 몇번째 재료들을 선택한 건지 알아내기 위해서는
0101 & (1<<i) 가 0인지 아닌지 확인하면 된다.

0101 & (1<<0) == 0001 (0아님 -> 0번째 재료 선택O)
0101 & (1<<1) == 0000 (0임 -> 1번째 재료 선택X)
0101 & (1<<2) == 0100 (0아님 -> 2번째 재료 선택O)
0101 & (1<<3) == 0000 (0임 -> 3번째 재료 선택X)

 

재료가 총 N개 이므로
1(00..001)부터 2^N-1(11..111)까지 순회하며 각각을
(1<<0) ... (1<<N-1)와 & 연산 하여 재료 선택 여부를 체크하고
문제 상황에 맞게 필요한 코드를 작성하면 된다.

 

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

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

    int ans=2147483647;
    vector<pair<int,int>> v;

    int n; cin>>n;
    for(int i=0; i<n; i++){
        int a,b; cin>>a>>b;
        v.push_back({a,b});
    }


    for(int i=1; i<(1<<n); i++){ // 1(00..001) 부터 2^n-1(11..111)까지 (n자리수)
        int a=1, b=0;
        for(int x=0; x<n; x++){ // 최대 n-1칸 shiftleft
            if(i & (1<<x)){ //조건문 결과가 1이면 해당 재료 사용한거임 
                a*= v[x].first;
                b+= v[x].second;
            }
        }
        ans=min(ans, abs(a-b));
    }
    cout<<ans;
    return 0;
}