#14888번 연산자 끼워넣기 (c++)

문제 링크 : www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

전형적인 백 트래킹 문제.

bool문으로 방문 여부를 확인하지 않고 오로지 if문을 통해 풀 수 있던 점이 편해서 좋았다.

 

#include <iostream>
#include <climits>
using namespace std;

int n=0, mini = INT_MAX, maxi = INT_MIN, arr[12] = {0,}, pl=0, mi=0, mul=0, di=0;

void dfs(int sum, int pl, int mi, int mul, int di, int index){
    if(pl==0&&mi==0&&mul==0&&di==0){
        if(sum<mini) mini = sum;
        if(maxi<sum) maxi = sum;
        return;
    }
    if(pl!=0) dfs(sum+arr[index],pl-1,mi,mul,di,index+1);
    if(mi!=0) dfs(sum-arr[index],pl,mi-1,mul,di,index+1);
    if(mul!=0) dfs(sum*arr[index],pl,mi,mul-1,di,index+1);
    if(di!=0) dfs(sum/arr[index], pl,mi,mul,di-1,index+1);   
}

int main(void) {
    cin >> n;
    for(int i=1; i<=n; i++) cin >> arr[i];
    cin >> pl >> mi >> mul >> di;
    if(pl!=0) dfs(arr[1]+arr[2],pl-1,mi,mul,di,3);
    if(mi!=0) dfs(arr[1]-arr[2],pl,mi-1,mul,di,3);
    if(mul!=0) dfs(arr[1]*arr[2],pl,mi,mul-1,di,3);
    if(di!=0) dfs(arr[1]/arr[2], pl,mi,mul,di-1,3);
    cout << maxi << "\n" << mini << "\n"; 
   return 0;
}