[삼성 기출 문제] 백준 14888 연산자 끼워넣기

문제 링크

클릭시 문제로 이동합니다.

어떻게 풀까?

다행히도 연산자의 우선 순위가 모두 같기 때문에, 앞에서부터 차례차례로 처리하면 됩니다!

그리고, 더하기, 빼기, 곱하기, 나누기 연산의 개수가 나옵니다.

그렇다는 것은, 현재 계산된 수에서 다음 수를 더하기, 빼기, 곱하기, 나누기 중 하나를 선택하고, 다음 수와 계산한 뒤에, 이렇게 계산된 수와 최댓값, 최솟값을 비교해서 계속 갱신해줍시다.

이렇게 모든 경우의 수를 다 구해서 저장된 최댓값과 최솟값을 출력하면 문제의 답을 출력할 수 있습니다!

3
3 4 5
1 0 1 0

위 예제를 통해서 한번 살펴봅시다.

처음에 더하기의 개수가 존재하기 때문에, 더하기의 개수를 하나 깎은 후에 3과 4를 더합니다.

다음에 더하기와 빼기의 개수가 0개이므로, 이 부분들은 넘어갑니다.

그리고, 곱하기의 개수가 0보다 크기 때문에, 곱하기의 개수를 하나 깎은 후에 3과 4를 더했던 7에 5를 곱합니다. 그렇게 35를 얻을 수 있습니다.

모든 수의 연산을 했으므로, 최종 결과인 35를 MAX와 MIN에 저장합니다.

그리고 이제 곱하기의 개수를 다시 하나 늘리고, 나누기 연산을 수행해보려고 했지만, 나누기 연산을 할 수 없으므로, 이제 처음에 했던 더하기 연산의 개수를 하나 늘려주고 맨 처음으로 돌아갑니다.

마찬가지로, 빼기 연산 개수가 없으므로 곱하기 연산을 수행합니다.

3과 4를 곱하면 12가 됩니다!

이제 더하기를 선택하면, 12+5= 17입니다.

현재 MAX는 35 그대로이고, MIN은 17로 변경합니다.

할 수 있는 모든 연산을 수행했기 때문에 MAX는 35, MIN은 17입니다!

이렇게 해서 dfs와 백트래킹을 이용하면 MAX와 MIN의 값을 구할 수 있습니다!

코드

#include<iostream>
 
using namespace std;
 
int nums[11];
int opers[4];
int res[2] = {(int)0x80000000, 0x7fffffff};
int n;
 
void f(int depth, int num){
    if(depth == n){
        res[0] = res[0] < num ? num : res[0];
        res[1] = res[1] > num ? num : res[1];
        return;
    }
 
    for(int i = 0; i < 4; i++){
        if(opers[i]){
            opers[i]--;
            switch(i){
                case 0:
                    f(depth+1, num+nums[depth]);
                break;
                case 1:
                f(depth+1, num-nums[depth]);
                break;
 
                case 2:
                f(depth+1, num*nums[depth]);
                break;
 
                case 3:
                f(depth+1, num/nums[depth]);
                break; 
            }
            opers[i]++;
        }
    }
}
 
int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> nums[i];
    for(int i = 0; i < 4; i++) cin >> opers[i];
 
    f(1, nums[0]);
    cout << res[0] << '\n' << res[1];
 
    return 0;
}

시간복잡도

dfs를 진행할때마다 4개의 분기점이 나올수 있기 때문에 시간복잡도는 입니다.