[14888] 연산자 끼워넣기(C++)

문제

14888번: 연산자 끼워넣기

 

 

해결 방법

우선 연산자의 입력값을 숫자로 대치하여 operators 배열에 저장해주었다.

• + : 0
• - : 1
• x : 2
• / : 3

위와 같이 설정하여 예를 들어 연산자 개수의 입력이 "2 0 1 0" 이라면 +, +, x 라는 뜻이므로, operators 배열에는 0, 0, 2가 저장된다.

 

입력된 숫자의 순서는 변경할 수 없기 때문에 가능한 연산자 순열의 모든 경우를 구해서 계산을 해줘야 하는데

이 때 <algorithm> 헤더에 내장되어 있는 next_permutation() 함수를 사용하였다.

 

이 함수의 원형은 

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

위와 같고 인자는 각각 순열의 시작 주소와 끝 주소이다.

 

예를 들어, 1-2-3-4에서 next_permutation을 사용하면 배열의 값이 1-2-4-3으로 바뀌고 잘 바뀌었다는 뜻으로 true를 반환한다.

하지만, 더 이상 구할 수 있는 다음 순열이 없다면 모든 경우를 다 구했다는 뜻으로 false를 반환한다.

 

순열을 구했으면 이제 계산을 하면 되는데, 

숫자의 개수보다 연산자의 개수가 1개가 적으므로 개수를 통일해주기 위하여 연산자 배열의 맨 처음에 '+'을 뜻하는 0을 추가해주었다.

맨 처음에 오는 숫자는 무조건 더해줘야 하기 때문이다!

 

예를 들어,

위와 같이 입력받은 경우, operators 배열의 맨 앞에 0을 추가하면

 

이렇게 되고 for문을 돌면서 sum을 계산해주면 된다.

 

이때 주의할 점은 이미 main에서 얻은 순열에다가 compute() 함수 내에서 임의로 0을 추가해준 것이기 때문에 

compute() 함수가 끝나기 전에 다시 0을 제거해줘야 그 다음 순열이 제대로 만들어진다.

그렇지 않으면 next_permutation이 0까지 추가해버린 상태에서 다음 순열을 찾아주기 때문에 이상한 값이 나오게 된다. 

 

그리고 이 중에서 최대, 최솟값을 찾아 답으로 출력하면 끝@

 

 

내 코드(C++)

// [14888] 연산자 끼워넣기
// https://www.acmicpc.net/problem/14888
// 브루트 포스

#include <cstdio>
#include <vector>
#include <algorithm> // next_permutation()
using namespace std;

vector <int> operators;
int a[12];
int compute(int n);

int main(void)
{
    int n, cnt, max = -1000000000, min = 1000000000;
    scanf("%d", &n);
    
    for(int i = 0 ; i < n ; i++) {
        scanf("%d", &a[i]);
    }

    // index 0 = '+', 1 = '-', 2 = '*', 3 = '/'
    for(int i = 0 ; i < 4 ; i++) {
        scanf("%d", &cnt);
        for(int j = 0 ; j < cnt ; j++) {
            operators.push_back(i);
        }
    }

    do{
        if(compute(n) > max) {
            max = compute(n);
        }
        
        if(compute(n) < min) {
            min = compute(n);
        }
	} while(next_permutation(operators.begin(),operators.end()));

    printf("%d\n%d\n", max, min);
}

int compute(int n)
{
    int sum = 0;
    operators.insert(operators.begin(), 0); // 맨 처음 숫자는 무조건 더해줘야 함
    
    for(int i = 0 ; i < n ; i++) {
        switch (operators[i]) {
        case 0:
            sum += a[i];
            break;
        case 1:
            sum -= a[i];
            break;
        case 2:
            sum *= a[i];
            break;
        case 3:
            sum /= a[i];
            break;
        default:
            break;
        }
    }
    
    operators.erase(operators.begin());
    return sum;
}