DeveloperOC

🔗 문제

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

📌 문제 요약

입력: 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, …, AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
출력: 첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다.

💡 접근 방법

순서가 고정된 N개의 수와 4가지의 연산자를 통해 최댓값과 최솟값을 구해야 했을 때,
하나의 연산식을 완성 시켰을 때 나오는 값을 최댓값과 최솟값에 비교하여 대입해주는 방식으로 풀어야 할 것 같다고 생각했다.

연산자 순서에 따라 계산 결과가 항마다 달라지기 때문에 모든 연산을 끝내고 비교해야 할 필요가 있다.
브루트 포스 알고리즘을 통해 모든 계산을 실행한다.

재귀함수를 통한 모든 경우의 수를 탐색하여 값 찾기.

⚠️ 처음에 했던 실수

시간을 줄여보고자 재귀함수 진입시 조건을 걸어 탈출하게 구상했었다.

💻 코드

#include <iostream>
#include <limits.h>
using namespace std;

int N;
int A[12];
int sign[4] = {0,0,0,0};
int maxV = INT_MIN;
int minV = INT_MAX;
void dfs(int value, int index)
{
    if(index == N - 1)
    {
        if(maxV < value)
            maxV = value;
        if(minV > value)
            minV = value;

    }

    for(int i = 0; i < 4; ++i)
    {
        if(sign[i] == 0)
            continue;
        sign[i]--;
        switch(i)
        {
            case 0:
                dfs(value + A[index + 1], index + 1);
                break;
            case 1:
                dfs(value - A[index + 1], index + 1);
                break;
            case 2:
                dfs(value * A[index + 1], index + 1);
                break;
            case 3:
                dfs(value / A[index + 1], index + 1);
                break;
        }
        sign[i]++;
    }
}
int main()
{
    cin >> N;
    for(int i = 0; i < N; ++i)
        cin >> A[i];

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


    dfs(A[0], 0);

    cout << maxV << "\n" << minV;
    return 0;
}