도영이가 만든 맛있는 음식 (feat. 백준, 2961번)

도영이가 만든 맛있는 음식
https://www.acmicpc.net/problem/2961

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

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;
int N, ans;
pair<int, int> arr[10], tmp[10];
bool visit[10];
void dfs(register int i, register int n){
    if(0 < n && n <= N){
        register int s = tmp[0].first, b = tmp[0].second;
        for(register int x = 1; x < n; ++x)
            s *= tmp[x].first, b += tmp[x].second;
        if(abs(s - b) < ans)
            ans = abs(s - b);
    }
    for(register int idx = i; idx < N; ++idx)
        if(!visit[idx]){
            visit[idx] = true;
            tmp[n] = arr[idx];
            dfs(idx + 1, n + 1);
            visit[idx] = false;
        }
}
int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    memset(visit, false, sizeof(visit));
    ans = 999999999;
    cin >> N;
    for(register int n = 0; n < N; ++n)
        cin >> arr[n].first >> arr[n].second;
    dfs(0, 0);
    cout << ans;
	return 0;
}
// *&)*@*

 

반응형

N개의 리스트에 대해서 1~N개의 조합을 구한 뒤, 신맛과 쓴맛 각각 연산하여 차이의 절대값이 가장 작은 값을 구해줍니다.