[C++] 연산자 끼워넣기

백준 14888번

 

문제 읽으면서 쉽게 풀수있도록 많이 신경써준 문제라는 느낌이 들었다

먼저 연산자 우선순위 고려도 안해도 되었고 중간에 계산되는 식도 int범위를 초과하지 않는다고 친절히 알려주었다

아마 그래서 solved ac 실버로 측정된 것 같다ㅎㅎ

삼성 SW 기출 문제집에 있는 몇안되는 실버 문제

 

dfs 순열 코드를 응용해서 작성해봤다

숫자 배열은 그대로 두고 그 사이사이에 어떤 연산자가 들어갈지를 전부 찾아주었다

이때 연산자 순서는 직관적으로 확인할 수 있게 string으로 그냥 넣어주었다

 

전체 숫자 사이에 연산자들이 정해지면 결과를 차례로 계산하여 최소,최대값과 비교해주었다

마지막에 최소값과 최대값만 출력해주면 끝!

 

#include <stdio.h>
#include <string>
 
using namespace std;
 
int N;
int c[5];
int operators[5];
int arr[105];
int MAX = -1000000000;
int MIN = 1000000000;
 
void dfs(int cnt,string str){
    if(cnt+1==N) {
        int len = str.length(),res = arr[0];
        for(int i = 0 ; i < len; i++){
            switch (str[i])
            {
            case '+':
                res += arr[i+1];
                break;
            case '-':
                res -= arr[i+1];
                break;
            case '*':
                res *= arr[i+1];
                break;
            case '/':
                res /= arr[i+1];
                break;
            }
        }
        if(MIN>res) MIN = res;
        if(MAX<res) MAX = res;
        return;
    }
    for(int i = 0 ; i < 4 ; i++){
        if(c[i]<operators[i]){
            c[i]++;
            if(i==0) dfs(cnt+1,str+"+");
            else if(i==1) dfs(cnt+1, str+"-");
            else if(i==2) dfs(cnt+1,str+"*");
            else dfs(cnt+1,str+"/");
            c[i]--;
        }
    }
}
 
int main(){
    scanf("%d",&N);
    for(int i = 0 ; i < N ; i++) scanf("%d",&arr[i]);
    for(int i = 0 ; i < 4 ; i++) scanf("%d",&operators[i]);
 
    dfs(0,"");
    printf("%d\n%d\n",MAX,MIN);
}