[백준 14888] 알고리즘 20일차 : 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

백트래킹 C++

삼성 SW 역량 테스트 기출 문제 1

 

문제

순서가 정해진 피연산자들이 주어지고 +,-,x,÷ 의 개수가 입력된다.

그럼 연산자들의 순서를 바꿔가며 계산한 값의 최댓값과 최솟값을 출력하는 문제이다.

 

접근방법

순서가 다르게 연산자들을 나열한다.

N과 M(1)의 코드를 재사용했다. 

그 결과 연산자들의 순서가 다른 모든 경우의 연산자 순열을 얻을 수 있고

모든 경우의 연산자 순서에 대해 계산하면서 최댓값과 최솟값을 갱신한다.

 

원래 N과 M코드에선 중복되지 않은 1부터 N까지의 수를 나열하는 것이었다면

여기선 +,-,x,÷ 를 0,1,2,3으로 치환하여 배열에 담는다.

예를들어 각 연산자의 개수가 2개(+) 1개(-) 1개(x) 1개(÷) 이렇게 주어졌다면

seq배열에는 0(+),0(+),1(-),2(x),3(÷) 이 담긴다.

중복되는 순열이 발생할 수 있지만 따로 걸러내지 않고 계산해도 시간초과가 나진 않았다.

 

소스코드

#include <iostream>
using namespace std;
static int N;
bool ischeck[10] = {false,};
int seq[10];
int An[11];
int numOfOperator[4];
int operators[10];
int result;
int Min = 1000000000;
int Max = -1000000000;

void f(int cnt){
    if(cnt == N-1){
        result = An[0];
        for(int i = 0 ; i < N-1 ; i++){
            if(seq[i] == 0)
                result += An[i+1];
            else if(seq[i] == 1)
                result -= An[i+1];
            else if(seq[i] == 2)
                result = result * An[i+1];
            else
                result = result / An[i+1];
        }
        //계산 완료
        if(Min > result)
            Min = result;
        if(Max <= result)
            Max = result;
    }
    else{
        for(int i = 0 ; i < N-1 ; i++){
            if(!ischeck[i]){
                ischeck[i] = true;
                seq[cnt] = operators[i];
                f(cnt+1);
                ischeck[i] = false;
            }
        }
    }
}

int main(){
    cin >> N;
    for(int i = 0 ; i < N ; i++)
        cin >> An[i];
    int cnt = 0;
    for(int i = 0 ; i < 4 ; i++){
        cin >> numOfOperator[i];
        for(int j = 0 ; j < numOfOperator[i]; j++)
            operators[cnt++] = i;
    }
    cnt = 0;
    f(cnt);
    cout << Max << "\n" << Min;
    return 0;
}