[백준/C++] 14888번 연산자 끼워넣기

백준

 

---

🤔문제 이해

중복이 존재하고, 순서에 상관있게 나열하는 연산자 순열의 모든 경우에 대해 계산한 값의 최솟값과 최댓값을 찾는 문제이다.

---

💡첫번째 아이디어

브루트 포스, 즉 모든 경우의 수를 찾아보고 계산해 비교해봐야 최솟값과 최댓값을 찾을 수 있겠다고 생각했다. 

모든 경우를 트리 모양으로 나타내보면 n번째 연산 다음에 올 수 있는 연산들은 n번째 연산이라는 공통된 값을 가지고 연산을 수행하므로 DFS를 이용해 풀면 될 것 같았다.

계산 결과나 계산 도중에 나오는 값들은 정수형인 int의 범위 안에 들어가므로 변수는 int로 선언하고, N의 범위가 11 이하이므로 이 아이디어로는 시간 초과 걱정은 없음!

 

 

🔥풀이🔥

main에서 +, -, x, / 를 각각 한번씩 dfs 함수를 실행시켜 준다.

dfs함수는 연산자를 나타내는 idx, 몇번째 숫자까지 계산했는지를 나타내는 cnt, 계산 결과를 나타내는 result를 매개변수로 받는다.

마지막 숫자까지 연산을 마쳤으면(cnt==n) 그 결과를 최대,최소랑 비교해서 최댓값, 최솟값을 업데이트.

연산해야 할 숫자가 남았으면 더하기부터 나누기까지 4번의 for문을 도는데 연산자가 남아있는 연산자별로 result 값을 업데이트 해서 dfs를 재귀적으로 수행한다.

이때 연산자를 사용했음을 나타내기 위해 연산자 개수를 저장한 배열의 값을 -1해준다.

 

---

오랜만에 한번에 성공!

 

아래는 제출한 코드이다.

#include <iostream>

using namespace std;

int n;
int op[4];
int num[12];
int min_num = 1000000000;
int max_num = -1000000000;

void check(int x) {
    if (min_num > x) min_num = x;
    if (max_num < x) max_num = x;
}

void dfs(int idx, int cnt, int result) {
    if (cnt == n) {
        check(result);
        return;
    }
    for (int i = 0; i < 4; i++) {
        op[idx]--;
        if (op[i] > 0) {
            if (i == 0) dfs(i, cnt + 1, result + num[cnt]);
            else if (i == 1) dfs(i, cnt + 1, result - num[cnt]);
            else if (i == 2) dfs(i, cnt + 1, result * num[cnt]);
            else if (i == 3) {
                dfs(i, cnt + 1, result / num[cnt]);
            }
        }
        op[idx]++;

    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    };
    int pl, mi, mu, di;
    cin >> pl >> mi >> mu >> di;
    for (int i = 0; i < 4; i++) {
        op[0] = pl;
        op[1] = mi;
        op[2] = mu;
        op[3] = di;
        if (op[i] > 0) {
            if (i == 0) {
                dfs(0, 2, num[0] + num[1]);
            } else if (i == 1) {
                dfs(1, 2, num[0] - num[1]);
            } else if (i == 2) {
                dfs(2, 2, num[0] * num[1]);
            } else if (i == 3) {
                dfs(3, 2, num[0] / num[1]);
            }
        }
    }
    cout << max_num << "\n" << min_num;
}