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

백준의 연산자 끼워넣기(14888) 문제이다.

( 문제 바로가기 )

삼성 SW역량테스트 기출 문제라고 한다...

[ 문제풀이 ]

1) 숫자들이 주어지고, 주어진 숫자들 사이사이에 주어진 연산기호들의 갯수들을 이용해서 적절하게 넣어서

   최대 최소값을 찾아주면 되는 문제이다.

   재귀를 통해서 모든 경우의 수를 다해보면 되는 브루트포스 문제이다.

   먼저 본인은, 재귀 함수의 매개변수를 총 7개를 사용하였다.

   (+기호갯수, -기호갯수, *기호갯수, /기호갯수, 현재값, 다음Index번호, 사용된 연산기호 갯수)

   

   앞에 4개 변수들은, 처음에 모두 0으로 호출되어, 아직 사용할 수 있는 갯수가 남아있다면

   각각 하나씩 ++ 해주면서 호출해주었고, 현재값에는 사용된 연산기호에 따라 계산된 값이,

   다음 Index번호는 이 다음에 계산할 숫자를 가져오기 위해서 Index번호를, 마지막은 전체 연산기호갯수를 저장해으로써

   가장 마지막 매개변수가 N - 1개가 되면 계산을 하는 식으로 구현하였다.

   어렵지 않은 브루트포스 문제이다.

[ 소스코드 ]

#include<iostream>
#include<cmath>
 
#define endl "\n"
#define MAX 11
using namespace std;
 
int N;
int Arr[MAX];
int Plus, Minus, Multiple, Divide;
int Operator_Num, Max_Value, Min_Value;
 
void Input()
{
    Max_Value = -1000000001;
    Min_Value = 1000000001;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Arr[i];
    }
    cin >> Plus >> Minus >> Multiple >> Divide;
    Operator_Num = N - 1;
}
 
void DFS(int Pl, int Mi, int Mul, int Div, int Sum, int N_Idx, int Cnt)
{
    if (Cnt == Operator_Num)
    {
        if (Max_Value < Sum) Max_Value = Sum;
        if (Min_Value > Sum) Min_Value = Sum;
        return;
    }
 
    if (Pl < Plus) DFS(Pl + 1, Mi, Mul, Div, Sum + Arr[N_Idx], N_Idx+1, Cnt + 1);
    if (Mi < Minus) DFS(Pl, Mi + 1, Mul, Div, Sum - Arr[N_Idx], N_Idx + 1, Cnt + 1);
    if (Mul < Multiple) DFS(Pl, Mi, Mul + 1, Div, Sum * Arr[N_Idx], N_Idx + 1, Cnt + 1);
    if (Div < Divide) DFS(Pl, Mi, Mul, Div + 1, Sum / Arr[N_Idx], N_Idx + 1, Cnt + 1);
}
 
void Solution()
{
    DFS(0, 0, 0, 0, Arr[0], 1, 0);
    cout << Max_Value << endl << Min_Value << endl;
}
 
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;
}