백준 알고리즘 14888

입력 : 연산할 수열, 연산자별 사용 가능한 갯수

출력 : 연산 결과로 나온 경우의 수 중에서 최대값과 최솟값

 

풀이

1. 재귀함수 한 번은 배열의 숫자 사이에 연산자를 하나 넣어본 것과 같다.

2. 함수를 한번 호출해 연산자를 넣어 계산한 뒤 재귀호출

3. 수열의 맨 마지막 수를 지나치면 전역변수 maxR과 minR을 연산 결과값이랑 비교해 갱신하고 return.

4. 연산자 사용시 opSymbol에 남은 횟수를 갱신해야 함

 

소스코드

#include <iostream>
using namespace std;
 
int N;
int opSymbol[4];
int maxR, minR;
int arr[12];
 
void calcOne(int n, int median){
    if(n == N){
        if(maxR < median)
            maxR = median;
        if(minR > median)
            minR = median;
    }
    
    for(int i=0; i<4; i++){
        if(opSymbol[i] == 0)
            continue;
        
        opSymbol[i]--;
        switch(i){
            case 0:
            calcOne(n+1, median+arr[n]);
            break;
            case 1:
            calcOne(n+1, median-arr[n]);
            break;
            case 2:
            calcOne(n+1, median*arr[n]);
            break;
            case 3:
            calcOne(n+1, median/arr[n]);
            break;
        }
        opSymbol[i]++;
    }
}
 
int main() {
    cin>>N;
    for(int i=0; i<N; i++)
        cin>>arr[i];
    
    cin>>opSymbol[0]>>opSymbol[1]>>opSymbol[2]>>opSymbol[3];
    
    maxR = -2000000000;
    minR = 2000000000;
    
    calcOne(1, arr[0]);
    cout<<maxR<<endl;
    cout<<minR<<endl;
    
    return 0;
}