[백준]연산자 끼워넣기

삼성 코딩테스트 기출문제 중 하나라는 연산자 끼워넣기 문제를 풀어보았다. 블로그 업데이트가 조금 늦었는데 최근에 코딩 테스트도 보고 다른것도 공부하다보니 늦어졌던거같다. 앞으로는 다시 각성해서 많이 풀어봐야겠고 최근에 풀었던 코딩 테스트를 기준으로 조금은 자신감이 생겼다.

이 문제는 + - * % 가 주어졌을때 해당 연산자의 숫자를 이용해서 만들수 있는 최대값과 최소값을 리턴하면 되는 문제이다. 언뜻보면은 어려워 보이는 문제지만 사실 backtracking 의 기본원리와 permutation 방식을 안다면 꽤 쉽게 풀수있는 문제이다. 맨 마지막 줄에 있는 숫자들을 index 로 표현해서 풀이해 보면 0인덱스는 더하기 1인덱스는 빼기 2인덱스는 곱하기 3인덱스는 나누기를 표현한다.

#include <iostream>
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100010
using namespace std;

int N;
vector<int> nums;
vector<int> expression;

void Input(){
    cin >> N;
    vector<int> copy1(N,0);
    vector<int> copy2(4,0);
    for(int i = 0; i < N; i++){
        cin >> copy1[i];
    }
    for(int i = 0; i < 4; i++){
        cin >> copy2[i];
    }

    nums = copy1;
    expression = copy2;



}

void dfs(vector<int>& nums, vector<int>& expression,int& max_, int& min_,int curr_sum,int counter){
    if(counter >= nums.size()){
        //cout << curr_sum << ' '; 
        max_ = max(max_,curr_sum);
        min_ = min(min_,curr_sum);
        return; 
    }

    for(int i = 0; i < expression.size(); i++){
        if(expression[i] > 0){
            //cout << i << ' '; 
            switch(i){
                case 0:
                    curr_sum += nums[counter];
                    expression[i] -= 1;
                    dfs(nums,expression,max_,min_,curr_sum,counter+1);
                    curr_sum -= nums[counter];
                    expression[i] += 1;
                    break;
                case 1:
                    curr_sum -= nums[counter];
                    expression[i] -= 1;
                    dfs(nums,expression,max_,min_,curr_sum,counter+1);
                    curr_sum += nums[counter];
                    expression[i] += 1;
                    break;
                case 2:
                    curr_sum *= nums[counter];
                    expression[i] -= 1;
                    dfs(nums,expression,max_,min_,curr_sum,counter+1);
                    curr_sum /= nums[counter];
                    expression[i] += 1;
                    break;
                case 3:
                    curr_sum /= nums[counter];
                    expression[i] -= 1;
                    dfs(nums,expression,max_,min_,curr_sum,counter+1);
                    curr_sum *= nums[counter];
                    expression[i] += 1;
                    break;
            }
        }
    }
}

void Solution(){
    int max_ = INT_MIN;
    int min_ = INT_MAX;
    int curr_sum = nums[0];
    dfs(nums,expression,max_,min_,curr_sum,1);

    cout << max_ << ' ';
    cout << min_ << ' '; 
}


void Solve(){
    Input();
    Solution();
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

원래는 항상 캡쳐했는데 이렇게 올리는것도 꽤 괜찮은거같다. 분명 내 구성은 완벽했는데 원하는 답이 안나왔었는데 이유가 current_sum 을 call by referenc (&) 방식으로 넣었어서 이상한 답이 나왔었다. 이런 자잘한 실수를 줄여야하는데 한참 멀은거같다. 0, 1, 2, 3 은 swtich 와 case 로 다뤄줬으면서 나쁘지 않은 코드였던거같다.

배운점:
1. backtracking 의 원리 잊지말자
2. 자잘한 실수좀 하지말자