백준 14888번 연산자 끼워넣기

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

모든 경우의 수를 고려해야하기 때문에 DFS(Depth First Search)를 통해 해결하는 문제였습니다.

적절한 조건을 걸고 더하기, 빼기, 곱하기, 나누기를 진행하면 어렵지 않게 풀 수 있는 문제였습니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 1000000000 + 1;

 

int N;

int number[12], Operator[4];

int maxResult = -MAX, minResult = MAX;

 

void DFS(int plus, int minus, int multiply, int divide, int cnt, int sum)

{

        //연산자를 모두 사용하였을 경우

        if (cnt == N)

        {

                 maxResult = max(maxResult, sum);

                 minResult = min(minResult, sum);

        }

       

        //모든 경우를 고려

        if (plus > 0)

                 DFS(plus - 1, minus, multiply, divide, cnt + 1, sum + number[cnt]);

        if (minus > 0)

                 DFS(plus, minus - 1, multiply, divide, cnt + 1, sum - number[cnt]);

        if (multiply > 0)

                 DFS(plus, minus, multiply - 1, divide, cnt + 1, sum * number[cnt]);

        if (divide > 0)

                 DFS(plus, minus, multiply, divide - 1, cnt + 1, sum / number[cnt]);

}

 

int main(void)

{

        cin >> N;

        for (int i = 0; i < N; i++)

                 cin >> number[i];

        for (int i = 0; i < 4; i++)

                 cin >> Operator[i];

 

        DFS(Operator[0], Operator[1], Operator[2], Operator[3], 1, number[0]);

 

        cout << maxResult << endl;

        cout << minResult << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~