[삼성SW테스트] 백준 14888번 - 연산자 끼워넣기 (정답률 47%)

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

14888번: 연산자 끼워넣기

삼성 SW테스트 기출문제다.

이 문제 역시 브루트포스로 해결할 수 있는 문제다. 이런 문제는 10분을 넘기면 곤란하다.

부호가 들어갈 수 있는 자리수가 최대 10자리 이므로, 10! 은 대략 360만번 연산을 소요한다. (엄밀히는 조합이므로 더 적지만 무시하더라도). 1억번을 1초라고 생각해도 충분히 돌아갈 수 있는 시간이므로 나는 next_permutation을 이용해 문제를 풀었다.

 

아래는 코드 전체. (0ms)

 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
int max_answer = -INF;
int min_answer = INF;
int N;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    vector<int> A(N, 0);
    vector<char> sign;
    for (int i = 0; i < N; i++){
        cin >> A[i];
    }
    int buho_num;
    for (int i = 0; i < 4; i++){
        cin >> buho_num; // +, -, x, / 개수
        for (int j = 0; j < buho_num; j++){
            if (i == 0)
                sign.push_back('p');
            else if (i == 1)
                sign.push_back('m');
            else if (i == 2)
                sign.push_back('g');
            else
                sign.push_back('d');
        }
    }
    sort(sign.begin(), sign.end());
    do{
        int cur_value = A[0];
        for (int i = 1; i < N; i++){
            int cur_sign = sign[i-1];
            int next_num = A[i];
            if (cur_sign == 'p')
                cur_value += next_num;
            else if (cur_sign == 'm')
                cur_value -= next_num;
            else if (cur_sign == 'g')
                cur_value *= next_num;
            else if(cur_sign == 'd'){
                if (cur_value < 0){
                    int temp = -cur_value;
                    temp /= next_num;
                    cur_value = -temp;
                }
                else
                    cur_value /= next_num;
            }
        }
        min_answer = min(min_answer, cur_value);
        max_answer = max(max_answer, cur_value);
    } while (next_permutation(sign.begin(), sign.end()));
 
    cout << max_answer << '\n' << min_answer << '\n';
    return 0;
}