14888번

14888번 - 연산자 끼워넣기

삼성 sw역량테스트 문제라는데, 나는 본 적 없으니 CE/IM 문제인 것 같다.

완전탐색을 이용하면 쉽게 풀리는 문제다.

단 나는 처음에 maxx 값을 0으로 초기화해서 시간이 지체했다.

값이 -10억까지 나올 수 있으므로 그 미만의 값으로 초기화했어야 했다.

<정답 코드>

#include<iostream>
#include<algorithm>
 
using namespace std;
int A[12];
int have[4];
int n;
int maxx = -987654321;
int minn = 987654321;
void dfs(int num,int sum)
{
    if (num == n-1)
    {    
        maxx = max(maxx, sum);
        minn = min(minn, sum);
        return;
    }
 
 
    for (int i = 0; i < 4; i++)
    {
        if (have[i] != 0)
        {
            if (i == 0)
            {
                have[i]--;
                dfs(num + 1, sum + A[num + 1]);
                have[i]++;
            }
            else if (i == 1)
            {
                have[i]--;
                dfs(num + 1, sum - A[num + 1]);
                have[i]++;
            }
            else if (i == 2)
            {
                have[i]--;
                dfs(num + 1, sum * A[num + 1]);
                have[i]++;
            }
            else
            {
                int temp;
                have[i]--;
                if (sum < 0)
                {
                    temp = -((-sum) / A[num + 1]);
                }
                else
                {
                    temp = sum / A[num + 1];
                }
                dfs(num + 1, temp);
                have[i]++;
            }
        }
    }
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &A[i]);
    }
 
    for (int i = 0; i < 4; i++)
    {
        scanf("%d", &have[i]);
    }
 
    dfs(0,A[0]);
 
    printf("%d\n%d\n", maxx, minn);
    return 0;
}