[BOJ] 14888번: 연산자 끼워넣기

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

n<= 11이기 때문에 전체 탐색으로 풀 수 있다. 어떻게 코딩해야 할지 감조차 오질 않아서 고생했다. 이런 문제들은 코딩 실력을 기르는데 좋은 것 같다라는 생각을 한다.

연산자들을 OP 배열에 받고 calc()에서 연산자들을 모두 돌면서 계산을 하는데, 우리는 모든 경우를 다 했을 때 최댓값을 구해야 하기 때문에 백트래킹을 해줘야 한다. 즉, 재귀 호출 이후에 나오는 ++OP[k]; 들의 역할이 백트래킹의 역할이다.(다시 되돌려 놓고 계산하는 것)

백트래킹, 브루트포스 문제들도 많이 풀어봐야 겠다.

소스코드

#include <cstdio>
#include <algorithm>
using namespace std;

int N, A[12], OP[4];
int Max = -1e9;
int Min = 1e9;

void calc(int cnt, int v) {
    if (cnt == N) {
        Max = max(Max, v);
        Min = min(Min, v);
        return;
    }
    if (OP[0]) {
        --OP[0];
        calc(cnt + 1, v + A[cnt]);
        ++OP[0];
    }
    if (OP[1]) {
        --OP[1];
        calc(cnt + 1, v - A[cnt]);
        ++OP[1];
    }
    if (OP[2]) {
        --OP[2];
        calc(cnt + 1, v * A[cnt]);
        ++OP[2];
    }
    if (OP[3]) {
        --OP[3];
        calc(cnt + 1, v / A[cnt]);
        ++OP[3];
    }
}

int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
    for (int i = 0; i < 4; ++i) scanf("%d", &OP[i]);
    
    calc(1, A[0]);
    printf("%d\n%d", Max, Min);
    return 0;
}