[BOJ 14888] 연산자 끼워넣기

1. 문제 설명

 

2. 구현 아이디어 1 - 틀렸습니다

가장 먼저 생각난 풀이는 순열로 가능한 식을 모두 구한 후, 최댓값과 최솟값을 갱신하는 것이였다.

연산자는 최대 N-1(=10)개가 있고, 10! = 3628800이므로 시간 제한도 넉넉하다.

 

코드 로직은 아래와 같다.

1. next_permutation으로 순열을 구한다
2. 순열로 구한 연산자 순서에 따라 식의 결과를 갱신한다
  - ret = v[0]
  - 반복문을 돌면서 ... ret = ret (연산자) v[i+1]
3. ret과 mx, mn(최댓값과 최솟값을 담는 변수)를 비교하여 최댓값과 최솟값을 갱신한다

 

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321

int calculate(int a, int b, int cmd) {
    switch (cmd) {
        case 0:
            return a + b;
        case 1:
            return a - b;
        case 2:
            return a * b;
        case 3:
            return a / b;
        default:
            return 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; // 수의 개수
    cin >> n;

    vector<int> v = vector<int>(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    vector<int> operators;

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    for (int i = 0; i < a; ++i) {
        operators.push_back(0); // +
    }
    for (int i = 0; i < b; ++i) {
        operators.push_back(1); // -
    }
    for (int i = 0; i < c; ++i) {
        operators.push_back(2); // *
    }
    for (int i = 0; i < d; ++i) {
        operators.push_back(3); // /
    }

    int mx = 0;
    int mn = INF;

    // 1. next_permutation으로 순열을 구함
    sort(operators.begin(), operators.end());

    // 2. 순열로 구한 연산자 순서에 따라 식의 결과 계산
    // 3. 최댓값과 최솟값 갱신
    do {
        int ret = v[0];
        for (int i = 0; i < operators.size(); ++i) {
            ret = calculate(ret, v[i+1], operators[i]);
        }

        mx = max(mx, ret);
        mn = min(mn, ret);
    } while (next_permutation(operators.begin(), operators.end()));

    cout << mx << "\n" << mn << "\n";

    return 0;
}

 

3. 구현 아이디어 2 - 맞았습니다!!

글 읽기 - << 테스트 케이스 공유 >>

 

질문 게시판의 반례를 참고하여 틀린 부분을 찾을 수 있었다.

• 연산 결과는 최대 10억이 가능하지만 INF(=987654321)이므로 10억보다 작다
• 연산 결과가 음수가 나올 수 있으므로 mx는 0부터 시작하면 안된다

 

아래와 같이 mx, mn을 int 범위의 최솟값과 최댓값으로 초기화하도록 코드를 수정하여 해결할 수 있었다.

int mx = INT_MIN;
int mn = INT_MAX;

 

 

 

나는 next_permutation을 사용하였는데, 다른 사람들의 풀이를 찾아보니 DFS, 백트래킹 등 재귀를 사용해서 푼 사람도 많았다.