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

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

14888번: 연산자 끼워넣기

 

내 풀이가 좋은 풀이는 아닌 것 같다. 그래도 우선 풀어야 하기 때문에... 생각나는대로 풀었다.

​

가능한 연산자 조합을 구하는 문제이므로 next_permutation을 썼다. 연산자 종류를 operators라는 벡터에 삽입한 후에, 연산자의 모든 조합으로 계산을 해주고 각각의 경우에 최대값과 최소값을 초기화해줬다.

​

다른 방법으로 DFS로 푸는 방법이 있다. 원리는 완전하게 동일한데 재귀 함수를 쓰기 때문에 코드가 짧아진다는 점... DFS 방법은 아래쪽에 있다👇

 

 

// 1. 무지성 풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    
    int* nums = new int[N]; // 연산되는 숫자 배열
    for(int i = 0; i < N; i++)
        cin >> nums[i];
    
    vector<int> operators; // 연산자 벡터
    
    int cnt;
    for(int i = 0; i < 4; i++){
        // 0(+), 1(-), 2(*), 3(/)
        cin >> cnt;
        for(int j = 0; j < cnt; j++)
            operators.push_back(i);
    }
    // 이미 오름차순 정렬된 상태
    
    int max = -1000000000;
    int min = 100000000;
    int idx, result;
    do {
        idx = 1;
        result = nums[0];
        for (auto it = operators.begin(); it != operators.end(); it++){
            if(*it == 0){
                result += nums[idx];
            }
            else if(*it == 1){
                result -= nums[idx];
            }
            else if(*it == 2){
                result *= nums[idx];
            }
            else if(*it == 3){
                result /= nums[idx];
            }
            idx++;
        }
        if(result < min)
            min = result;
        if(result > max)
            max = result;
    } while (next_permutation(operators.begin(), operators.end()));
    
    cout << max << endl << min << endl;
    
    delete[] nums;
    
    return 0;
}
​

 

// 2. DFS 풀이

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

int N;
int Max = -1000000000;
int Min = 1000000000;

void DFS(int plus, int minus, int mult, int div, int cnt, int sum, int nums[]) {
	if (cnt == N) {
		Max = max(Max, sum);
		Min = min(Min, sum);
	}

	if (plus > 0)
		DFS(plus - 1, minus, mult, div, cnt + 1, sum + nums[cnt], nums);
	if (minus > 0)
		DFS(plus, minus - 1, mult, div, cnt + 1, sum - nums[cnt], nums);
	if (mult > 0)
		DFS(plus, minus, mult - 1, div, cnt + 1, sum * nums[cnt], nums);
	if (div > 0)
		DFS(plus, minus, mult, div - 1, cnt + 1, sum / nums[cnt], nums);
}

int main() {

	cin >> N;
	int* nums = new int[N];
	
	for (int i = 0; i < N; i++)
		cin >> nums[i];

	int operators[4];
	for (int i = 0; i < 4; i++)
		cin >> operators[i];

	DFS(operators[0], operators[1], operators[2], operators[3], 1, nums[0], nums);

	cout << Max << endl << Min << endl;

	delete[] nums;

	return 0;
}