[구현 / BOJ 14888 / C++] 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

1) 연산자와 숫자를 각각의 배열에 담는다.
2) 연산자의 순열을 구한다.
3) 구한 순열의 각각의 경우에 대해 준비된 배열로 연산을 한다.
4) 연산값 중 최소값, 최대값을 저장한다.

오랜만에 제대로 풀린 문제 같다.... 이번 문제는 글에 써져있는 그대로 구현만 해내면 된다!! (물론 함정을 조심해야함)

 

연산도 앞에서부터 차례대로인점을 생각하자!

 

우선은 연산자의 개수는 N-1개로 고정돼있다. 즉, 연산자를 배열로 표현하면 된다!!

이때, A1을 숫자, op1을 연산자라고 하면, A1..An은 고정돼있고 op1..opn-1끼리만 움직인다.

결국 문제에서 말하고자 하는 것은 op끼리의 순서를 의미하는 것이다!

즉, op의 permutation(순열)을 구하면 된다.

 

순열을 구하고나면, 각각의 경우의 수에 대해 연산에 맞게 연산해주면 된다.

이때, 순서가 정해진 숫자들은 다른 배열(A)에 보관돼있으니, 이 정보를 활용해서 다음과 같이 연속적으로 연산을 해주면 된다.

손으로 써봤는데, 이 부분은 코드를 읽으면 이해가 빠를 것이다!

 

 

그리고, 음수까지 포함돼있음을 기억하자!!! ans_min을 0으로 뒀다가 한참 헤맸다... INT_MIN으로 두자!!

#include<bits/stdc++.h>
using namespace std;

int op[110], A[15], B[15], N;
int ans_mx=INT_MIN, ans_min=INT_MAX;

int cal(int n1, int oper, int n2){
    int res=0;
    
    if(oper==1){
        res = n1 + n2;
    }else if(oper==2){
        res = n1 - n2;
    }else if(oper==3){
        res = n1 * n2;
    }else if(oper==4){
        res = n1 / n2;
    }
    
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 0 ; i < N ; i++){
        cin >> A[i];
    }
    
    int now=0;
    for(int i = 1 ; i < 5 ; i++){ // 1 + 2 - 3 x 4 % 를 의미함.
        int tmp=0;
        cin >> tmp;
        for(int j = now ; j < now+tmp ; j++){
            op[j]=i;
        }
        now += tmp;
    } // 연산자 순서 설정.
    

    do{
        memcpy(B, A, sizeof(A)); // 배열 복사. A를 B에 담음.
        for(int i=0 ; i < N-1 ; i++) {
            
//            cout << B[i] << ' ' << op[i] << ' ' << B[i+1]; test 용
            B[i+1] = cal(B[i], op[i], B[i+1]); // cal 값을 그다음 값으로 넘겨줌.
//            cout << '=' << B[i+1] << '\n';
            
        }
        ans_mx = max(ans_mx, B[N-1]); // 정답1 구하기
        ans_min = min(ans_min, B[N-1]); // 정답2 구하기
        
        
    }while(next_permutation(op, op + N-1));
    
    cout << ans_mx << '\n' << ans_min << '\n';
    
}