[백준/백트래킹/C++] 14888번 연산자 끼워넣기 (삼성 SW 역량 테스트 기출)

문제집: 삼성 SW 역량 테스트 기출 문제 (baekjoon)

14888번: 연산자 끼워넣기

문제풀이 방법

1. 더하기, 빼기, 곱하기, 나누기를 각각 1, 2, 3, 4 로 지정하여 구별한다
2. n-1개의 연산으로 수열을 만든다
3. 계산
(처음에 음수는 생각을 못하고 maxVal = 0으로 초기화했더니 틀렸다,, 넓게 생각하기!!)

input() 함수 설명

void input(){
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];

    cin >> pl >> mi >> mu >> di; // 더하기, 빼기, 곱하기, 나누기

    for(int i=0; i<pl; i++) op.push_back(1); // 더하기 : 1
    for(int i=0; i<mi; i++) op.push_back(2); // 빼기 : 2
    for(int i=0; i<mu; i++) op.push_back(3); // 곱하기 : 3
    for(int i=0; i<di; i++) op.push_back(4); // 나누기 : 4
}

n을 입력받고, n개수만큼 수열 a를 입력받는다
그 뒤로 더하기, 빼기, 곱하기, 나누기의 개수를 입력받고
벡터 op에 더하기 개수만큼 1, 빼기 개수만큼 2, 곱하기 개수만큼 3, 나누기 개수만큼 4를 넣어준다

order() 함수 설명

void order(int tot){ // 연산 개수
    if(tot == n-1){
        cal();
        return;
    }

    for(int i=0; i<n-1; i++){
        if(!isused[i]){
            isused[i] = true;
            arr[tot] = op[i];
            order(tot+1);
            isused[i] = false;
        }
    }
}

연산이 1,2,3,4로 들어있는 op벡터에서 백트래킹을 이용하여 수열을 만들어 arr[] 배열에 넣어준다

cal() 함수 설명

void cal(){
    int result = a[0];
    for(int i=0; i<n-1; i++){
        if(arr[i]==1) result += a[i+1];
        else if(arr[i]==2) result -= a[i+1];
        else if(arr[i]==3) result *= a[i+1];
        else{
            if(result<0) result = ((-1*result)/a[i+1])*(-1);
            else result /= a[i+1];
        }
    }
    maxVal = max(maxVal, result);
    minVal = min(minVal, result);
}

result 값을 a[0]으로 초기화 해주고 arr[]의 값에 따라 연산해준다
연산이 끝나면 최대값과 최소값을 판별해 넣어준다

전체 코드

#include <iostream>
#include <vector>

using namespace std;
int n;
int a[12];
int arr[11]; // 연산 담기
int pl, mi, mu, di; // 더하기, 빼기, 곱하기, 나누기
vector<int> op;
bool isused[11];
int maxVal = -2e9, minVal = 2e9;

void cal(){
    int result = a[0];
    for(int i=0; i<n-1; i++){
        if(arr[i]==1) result += a[i+1];
        else if(arr[i]==2) result -= a[i+1];
        else if(arr[i]==3) result *= a[i+1];
        else{
            if(result<0) result = ((-1*result)/a[i+1])*(-1);
            else result /= a[i+1];
        }
    }
    maxVal = max(maxVal, result);
    minVal = min(minVal, result);
}

void order(int tot){ // 연산 개수
    if(tot == n-1){
        cal();
        return;
    }

    for(int i=0; i<n-1; i++){
        if(!isused[i]){
            isused[i] = true;
            arr[tot] = op[i];
            order(tot+1);
            isused[i] = false;
        }
    }
}

void input(){
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> a[i];

    cin >> pl >> mi >> mu >> di; // 더하기, 빼기, 곱하기, 나누기

    for(int i=0; i<pl; i++) op.push_back(1); // 더하기 : 1
    for(int i=0; i<mi; i++) op.push_back(2); // 빼기 : 2
    for(int i=0; i<mu; i++) op.push_back(3); // 곱하기 : 3
    for(int i=0; i<di; i++) op.push_back(4); // 나누기 : 4
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    order(0);

    cout << maxVal << '\n' << minVal;

    return 0;
}