문제 푼 날짜 : 2021-09-16

문제

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

접근 및 풀이

크게 어렵지 않은 백트래킹 문제였다.
dfs로 연산자를 하나씩 선택해나가면서 연산자에 따라 값을 계산해주었다.
그리고 N개의 연산자가 선택됐을 때, 계산된 최댓값과 최솟값을 업데이트해주면 된다.

백트래킹이 아닌 방법으로도 풀어봤다.
2020 카카오 인턴십 문제 중에 수식 최대화라는 문제가 있다.
이 문제와 비슷한 것 같아서 비슷하게 완전탐색으로도 구현해보았다.

코드 (백트래킹)

// 백준 14888번 : 연산자 끼워넣기
#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> opnd, optr;
int maxNum = -1000000000, minNum = 1000000000;

void dfs(int sum, int idx) {
    if (idx == N) {
        maxNum = max(maxNum, sum);
        minNum = min(minNum, sum);
        return;
    }
    for (int i = 0; i < 4; i++) {
        if (optr[i] > 0) {
            optr[i]--;

            if (i == 0) { // 덧셈
                dfs(sum + opnd[idx], idx + 1);
            } else if (i == 1) { // 뺄셈
                dfs(sum - opnd[idx], idx + 1);
            } else if (i == 2) { // 곱셈
                dfs(sum * opnd[idx], idx + 1);
            } else { // 나눗셈
                dfs(sum / opnd[idx], idx + 1);
            }
            optr[i]++;
        }
    }
}

int main() {
    cin >> N;

    opnd.resize(N);
    optr.resize(4);
    for (int i = 0; i < N; i++) {
        cin >> opnd[i];
    }
    for (int i = 0; i < 4; i++) {
        cin >> optr[i];
    }
    
    dfs(opnd[0], 1);

    cout << maxNum << '\n' << minNum;
    return 0;
}

코드 (완전탐색)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int calculate(int a, int b, char optr) {
    switch (optr) {
        case '+' :
            return a + b;
        case '-' :
            return a - b;
        case '*' :
            return a * b;
        case '/' :
            return a / b;
    }
}

int main() {
    int N;
    vector<int> opnd;
    vector<char> optr;

    cin >> N;
    for (int i = 0; i < N; i++) {
        int num;
        cin >> num;
        opnd.push_back(num);
    }

    for (int i = 0; i < 4; i++) {
        int cnt;
        char ch;
        cin >> cnt;
        if (i == 0) ch = '+';
        else if (i == 1) ch = '-';
        else if (i == 2) ch = '*';
        else if (i == 3) ch = '/';
        
        for (int j = 0; j < cnt; j++) {
            optr.push_back(ch);
        }
    }
    sort(optr.begin(), optr.end());
    int maxNum = -1000000000, minNum = 1000000000;

    do {
        vector<char> tmp_optr(optr.begin(), optr.end());
        vector<int> tmp_opnd(opnd.begin(), opnd.end());

        for (int i = 0; i < tmp_optr.size(); ) {
            tmp_opnd[i] = calculate(tmp_opnd[i], tmp_opnd[i + 1], tmp_optr[i]);
            tmp_opnd.erase(tmp_opnd.begin() + i + 1);
            tmp_optr.erase(tmp_optr.begin() + i);
        }
        maxNum = max(maxNum, tmp_opnd[0]);
        minNum = min(minNum, tmp_opnd[0]);
        
    } while (next_permutation(optr.begin(), optr.end()));

    cout << maxNum << '\n' << minNum;
    return 0;
}

결과

피드백

아직 백트래킹 문제를 푸는데 있어서 사고가 유연하지 못하다. 더 많은 문제를 풀어봐야 감이 잡힐 것 같다.