백준 2961 - 도영이가 만든 맛있는 음식 (C++)

알고리즘 거진 반년을 손 놓으니 뇌가 깨끗해져서 한시간 걸렸다...

 

브루트포스로 전형적인 재귀나 dfs로 풀어도 되지만, C++을 공부하고 비트마스킹을 다시 봤던 차라 비스마스킹으로 풀었다.

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

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

 

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    int i;
    cin >> i ;
    long long S[i];
    long long B[i];
    
    int idx = 0;
    long long result = 0;
    
    while(idx < i) {
        if (idx == 0) {result = abs(S[idx] - B[idx]);}
        cin >> S[idx] >> B[idx];
        result = min(result, abs(S[idx] - B[idx]));
        idx++;
    }
    //비트 마스킹을 이용해 브루트 포스 순회
    for(int j = 1; j < 1<<i ; j++) { //모든 수를 순회   
        long long sVal = 1;
        long long bVal = 0;
        for(int index = 0; index<i; index++) { // 한 비트씩 옮겨가며 1의 개수를 체크
            if(j & 1<<index) {
                sVal *= S[index];
                bVal += B[index];
            }
        }
        result = min(result, abs(sVal - bVal));
    }
    
    cout << result << "\n";
    return 0;
}