[백준] 14888번 연산자 끼워넣기

문제 링크: https://www.acmicpc.net/problem/14888

문제

문제 이해

입력은 첫번째 줄에 입력받을 숫자의 개수, 두번째 줄에 숫자들, 세번째 줄에 각 연산자들의 갯수가 차례대로 들어온다.
입력받은 숫자들의 순서는 건들이지 않고, 입력받은 연산자들을 모두 사용하여 최대값과 최소값을 구하는 것이다. 이때 연산자들의 우선순위는 무시한다.

문제 접근

앞서 풀었던 dfs문제들과 동일한 방식으로 풀면 된다. 여기서 바꿔야 될 점은 어떻게 연산자들을 표시하고, 그것들을 backtracking 할까이다. 그래서 나는 각 연산자들을 +,-,*,/ 차례대로 0,1,2,3으로 표시하여 각 입력받은 연산자들의 수대로 숫자로 넣어 문자열로 만들었다. 그리고 index를 사용하여, dfs를 사용하였다. 나머지는 전 포스트와 동일한 방법으로 구현하였다.

코드 구현(c++)

#include <iostream>
#include <vector>
#include <string>
#include <bits/stdc++.h>

using namespace std;

vector<int> result;
vector<int> check_symbol; // 여기 순서대로 symbols에 있는 거 빼서 쓰면 됨.  
bool check[10];
vector<int> symbols;// symbol들을 넣어 놓은 것,
vector<int> nums;//입력받은 숫자들
int num;

void cal(){
    int temp = 0;
    for(int i = 0 ; i < num - 1; i++){
        if(i == 0) temp = nums[i];
        if(symbols[check_symbol[i]] == 0){
            temp += nums[i+1];
        }
        else if(symbols[check_symbol[i]] == 1){
            temp -= nums[i+1];
        }
        else if(symbols[check_symbol[i]] == 2){
            temp *= nums[i+1];
        }
        else if(symbols[check_symbol[i]] == 3){
            temp /= nums[i+1];
        }
    }
    result.push_back(temp);
    
}

void dfs(int count){
    if(count == num-1){
        cal(); 
    }
    else{
        for(int i = 0; i < num - 1 ; i++){
            if(!check[i]){
                check_symbol.push_back(i);
                check[i] = true;
                dfs(count+1);
                check[check_symbol.back()] = false;
                check_symbol.pop_back();
            }
        }
    }
    return;
}
void make_symbol(int symbol_num[]){
    for(int i = 0 ; i < 4; i++){
        for(int j = 0 ; j < symbol_num[i] ; j++){
            symbols.push_back(i);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> num;
    int temp;
    int symbol_num[4] = {0,};
    for(int i = 0 ; i < num ; i++){
        cin >> temp;
        nums.push_back(temp);
    }
    for(int i = 0 ; i < 4 ; i++){
        cin >> temp;
        symbol_num[i] = temp;
    }
    make_symbol(symbol_num);
    dfs(0);
    sort(result.begin(),result.end());
    cout << result.back() << "\n";
    cout << result.front() << "\n";

}

평가

점점 dfs문제에 대한 자신감이 생겨나고 있는 것 같다. 앞으로 다른 알고리즘 문제에 대한 자신감도 붙으면 좋겠다.
vs code에서는 컴파일이 되지만, 백준에서는 컴파일이 안되는 일이 발생했다. 전에도 경험한 일이여서, 헤더파일의 부재를 깨닫고, 알맞은 헤더파일을 찾아서 넣으려고 했지만, 무엇을 넣어야할지 도무지 모르겠어서, 헤더파일의 마스터키같은 <bits/stdc++>를 넣어서 해결하였다.