[BOJ 14888 // C++] 연산자 끼워넣기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 14888번 문제인 연산자 끼워넣기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

이 문제에서 최댓값과 최솟값을 직접 구하는 공식을 만드는 것은 숫자가 어떤 규칙으로 들어올 지 알 수 없고, 순서를 바꿀 수 없으며, 연산의 개수도 알 수 없어 사실상 무리이다. 다행히 주어지는 숫자의 개수가 적으므로, 가능한 모든 연산자의 순열(permutation)을 구해 각 연산자의 순열에 대응되는 숫자를 모두 더해보는 방식으로 문제를 해결할 수 있다.

 

제출한 코드는 다음과 같이 구성되어있다.

 

1) void func() 함수

가능한 모든 연산자의 순열을 생성하는 함수이다. 각 연산자를 사용할 수 있는 횟수가 정해져있다는 것을 기억하고, 각 연산자가 남아있지 않다면 건너뛴다는 조건을 넣어주면 구현은 간단하다. 조건에 맞는 순열을 찾았다면, calc 함수를 부른다.

 

2) void calc() 함수

연산자의 순열이 주어졌을 때 수들 사이에 연산자들을 넣어 계산하고, 계산된 값이 최댓값 또는 최솟값인지 확인하는 함수이다. 계산 자체는 어려운 점이 없으므로 설명은 생략한다.

 

3) int main() 함수

코드가 동작하는 부분이다. 이 코드에는 데이터를 읽어오는 파트가 main에 들어있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::vector;

int arr[12]; // 주어지는 숫자들
int operation[4]; // 각 연산자의 개수

vector<int> oper; // 연산자의 순열을 담을 벡터

int N;

int mx = -1000000000, mn = 1000000000;

void calc() { // 연산자의 순열을 받았을 때 대응되는 값을 계산하는 함수
    int x = arr[1];
    int i = 2;
    for (vector<int>::iterator iter = oper.begin();iter != oper.end();iter++) {
        if (*iter == 0) x += arr[i];
        else if (*iter == 1) x -= arr[i];
        else if (*iter == 2) x *= arr[i];
        else x /= arr[i];
        i++;
    }
    if (x > mx) mx = x;
    if (x < mn) mn = x;
}

void func() { // 가능한 연산자의 순열을 생성하는 함수
    if (oper.size() == N - 1) calc();
    else {
        for (int i = 0;i < 4;i++) {
            if (operation[i] > 0) {
                oper.push_back(i);
                operation[i] -= 1;
                func();
                operation[i] += 1;
                oper.pop_back();
            }
        }
    }
}

int main()
{
    cin >> N;
    for (int i = 1;i <= N;i++) {
        int x; cin >> x;
        arr[i] = x;
    }
    for (int i = 0;i < 4;i++) {
        int x; cin >> x;
        operation[i] = x;
    }
    func();

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

    return 0;
}