[백준/BOJ] 14888번 연산자 끼워넣기 (C++)

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

삼성 역량 테스트 기출 문제 : DFS(순열, 조합)

DFS 또는 next_permutation()을 이용해 연산자의 순열을 구해야합니다. DFS를 사용할 시 조건문 쪽에서 else if를 쓰지 않도록 주의합니다.

 

#include <iostream>
using namespace std;

int a[12], op[4];
int n, ansMax = -2147000000, ansMin = 2147000000;

void DFS(int idx, int sum) {
    if(idx == n - 1) {
        ansMax = max(ansMax, sum);
        ansMin = min(ansMin, sum);
    } else {
        // 더하기 연산
        if(op[0] > 0) {
            op[0]--;
            DFS(idx + 1, sum + a[idx + 1]);
            op[0]++;
        }
        
        // 빼기 연산
        if(op[1] > 0) {
            op[1]--;
            DFS(idx + 1, sum - a[idx + 1]);
            op[1]++;
        }
        
        // 곱하기 연산
        if(op[2] > 0) {
            op[2]--;
            DFS(idx + 1, sum * a[idx + 1]);
            op[2]++;
        }
        
        // 나누기 연산
        if(op[3] > 0) {
            op[3]--;
            DFS(idx + 1, sum / a[idx + 1]);
            op[3]++;
        }
        
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    for(int i = 0; i < 4; i++) {
        cin >> op[i];
    }
    
    DFS(0, a[0]); // a의 인덱스, 연산 수행 후 합
    cout << ansMax << "\n" << ansMin;
}

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, ansMax = -2147000000, ansMin = 2147000000;
    cin >> n;
    int a[n];
    vector<int> op;
    
    for(int i = 0; i < n; i++) {
        cin>>a[i];
    }
    
    for(int i = 0; i < 4; i++) {
        int tmp;
        cin >> tmp;
        while(tmp--) {
        	op.push_back(i);
		}
    }
   
   sort(op.begin(), op.end());
   do {
   		int idx = 0;
   		int sum = a[0];
        // 연산자의 수는 항상 숫자의 수보다 1 적다
   		for(int i = 0; i < n - 1; i++) {
   			if(op[i] == 0) {
   				sum += a[++idx];
			} else if(op[i] == 1) {
				sum -= a[++idx];
			} else if(op[i] == 2) {
				sum *= a[++idx];
			} else {
				sum /= a[++idx];
			}
		}
		ansMax = max(ansMax, sum);
		ansMin = min(ansMin, sum);
   } while(next_permutation(op.begin(), op.end()));
   
   cout << ansMax << "\n" << ansMin;
}