BOJ 14888 : 연산자 끼워넣기 - C++

연산자 끼워넣기

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#define ll long long
#define ull unsigned long long
using namespace std;
// 1004 ~ 1022
int N, ansB=-1e9, ansS=1e9;
vector<int> v;
int cnt[4];
void func(int depth, int tot)
{
    if(depth == N){
        ansB = max(ansB, tot);
        ansS = min(ansS, tot);
        return;
    }
    for(int j=0;j<4;j++)
    {
        int prev = tot;
        if(cnt[j] == 0) continue;
        if(j == 0) tot += v[depth];
        else if(j == 1) tot -= v[depth];
        else if(j == 2) tot *= v[depth];
        else if(j == 3) tot /= v[depth];
        cnt[j]--;
        func(depth+1, tot);
        cnt[j]++;
        tot = prev;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i=0;i<N;i++)
    {
        int a;
        cin >> a;
        v.push_back(a);
    }
    for(int i=0;i<4;i++)
        cin >> cnt[i]; // + , -, x, /

    func(1,v[0]);
    cout << ansB << '\n';
    cout << ansS << '\n';
    return 0;
}
  • 핵심
    : 백트래킹을 이용해 연산자에 따라 모든 경우의 수수행

좋은 웹페이지 즐겨찾기