백준 14888 - 연산자 끼워넣기

 

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

14888번: 연산자 끼워넣기

문제 설명

---

수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 계산시 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산한다. N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구해라~

 

접근 방식

---

DFS를 활용하여 경우의 수를 모두 확인하면서 최대와 최소를 구하면 된다.

 

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n;
const int MAX = 1000000000 + 1;
int member[12], buho[4];
int maxResult = -MAX, minResult = MAX;

void dfs(int plus,int minus,int multi,int div,int cnt,int sum){
    if(cnt==n){
        maxResult = max(maxResult,sum);
        minResult = min(minResult,sum);
    }   
	//모든 경우를 고려
    if (plus > 0)
        dfs(plus - 1, minus, multi, div, cnt + 1, sum + member[cnt]);
    if (minus > 0)
        dfs(plus, minus - 1, multi, div, cnt + 1, sum - member[cnt]);
    if (multi> 0)
        dfs(plus, minus, multi - 1, div, cnt + 1, sum * member[cnt]);
    if (div > 0)
        dfs(plus, minus, multi, div - 1, cnt + 1, sum / member[cnt]);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>member[i];
    for(int i=0;i<4;i++) cin>>buho[i];
    dfs(buho[0],buho[1],buho[2],buho[3],1,member[0]);
    cout<<maxResult<<"\n";
    cout<<minResult<<"\n";
    return 0;
}

funny algorithm *0*!