BOJ14888 연산자 끼워넣기

문제

문제를 보자마자 순열 문제임을 알 수 있다. 사실 순열 문제가 난이도가 높지는 않지만 신경쓸 부분도 많고 코드를 외우고 있지 않으면 살짝 헷갈리는 부분도 있어서 나름(?) 난이도가 있다과 생각하는데 의외로 실버1 등급이라 살짝 흠칫함ㅋ..... (나만 어려운감 ㅋ)

어찌 되었든 이번 문제는 크게 두 가지에 대한 구현이 필요하다.

1. 입력받은 연산자를 배열 형태로 관리하고 이에 대한 순열을 생성
2. 생성된 모든 순열에서 연산을 수행하고 최대값, 최소값 업데이트

순열

c++에서 순열을 구현하기 위해서는 기본적으로 DFS를 사용하는데 여기서 DFS에 대한 구체적인 설명은 제외하고 DFS를 이용하여 순열을 구현하는 방법만 코드로 짧게 소개하면 아래와 같다.

void makeOperatorArray(int idx) {
    if(idx == total_num){
        max_result = max_result > cal() ? max_result : cal();
        min_result = min_result < cal() ? min_result : cal();
    }
    else {
        for(int i=0;i<total_num;i++) {
            if(checklist[i] == false){
                operator_array_perm[idx] = operator_array[i];
                checklist[i] = true;
                makeOperatorArray(idx+1);
                checklist[i] = false;
            }
        }
    }
}

코드에서 각 변수들은 다음과 같은 의미를 갖는다.

• idx = 내가 필요한 연산자의 수(nPr에서 r의 역할)
• total_num = 전체 연산자 수(문제에서는 N-1개가 된다)
• max_result, min_result = 최대, 최소 결과값
• cal() = 연산자 배열을 이용하여 실제 연산을 수행한 결과값을 반환하는 함수
• operator_array_perm[] = 연산자 순열 배열
• checklist[] = 순열 구현시 사용할 방문기록(..?)

대충 의미는 이렇게 되는데 아마 DFS에 대해 알고있다면 위 코드는 일반적인 DFS 코드와 차이가 없는 것을 알 수 있다. 차이가 있다면 재귀가 종료되었을 때 checklist를 다시 false로 바꿔주는 것 정도..?(이게 순열 구현하는 핵심임)

코드

#include <iostream>

using namespace std;

int N;
int operand[11];
int operator_totalnum[4];
int operator_array[10];
int operator_array_perm[10];

int total_num = 0;
int max_result = 0;
int min_result = 0;
bool checklist[10] = {false};

void input();
void makeOperatorArray(int);
int cal();
int eval(int, int);

int main() {
    input();

    makeOperatorArray(0);

    cout << max_result << endl << min_result;
    return 0;
}

void input() {
    cin >> N;

    for(int i=0;i<N;i++){
        cin >> operand[i];
    }
    int prev_j = 0;
    int j=0;
    for(int i=0;i<4;i++){
        cin >> operator_totalnum[i];
        total_num += operator_totalnum[i];
        for(j=prev_j;j<prev_j + operator_totalnum[i];j++){
            operator_array[j] = i;
        }
        prev_j = j;
    }
    
    int temp=operand[0];
    for(int i=0;i<total_num;i++){
        if(operator_array[i] == 0){
            temp = temp + operand[i+1];
        }
        else if(operator_array[i] == 1){
            temp = temp - operand[i+1];
        }
        else if(operator_array[i] == 2){
            temp = temp * operand[i+1];
        }
        else if(operator_array[i] == 3){
            temp = temp / operand[i+1];
        }
    }

    max_result = min_result = temp;
}

void makeOperatorArray(int idx) {
    if(idx == total_num){
        max_result = max_result > cal() ? max_result : cal();
        min_result = min_result < cal() ? min_result : cal();
    }
    else {
        for(int i=0;i<total_num;i++) {
            if(checklist[i] == false){
                operator_array_perm[idx] = operator_array[i];
                checklist[i] = true;
                makeOperatorArray(idx+1);
                checklist[i] = false;
            }
        }
    }
}


int cal() {
    int prev=operand[0];
    for(int i=0;i<total_num;i++){
        prev = eval(prev, i);
    }

    return prev; // 전체 계산 결과를 반환해준다. 
}

int eval(int prev, int i) {
    switch(operator_array_perm[i]){
        case 0 : return prev + operand[i+1];
        case 1 : return prev - operand[i+1];
        case 2 : return prev * operand[i+1];
        case 3 : return prev / operand[i+1];
    }

    return 0;
}

코드가 복잡하거나 길지 않아서 아마 이해하는 데는 어렵지 않겠지만 지금 맘에 들지 않는 부분이 저 input() 마지막 부분에 min_result, max_result의 초기값을 설정해주는 부분인데 저 부분은 조금 더 생각해보고 더 좋은 방법이 있으면 수정하고 싶당 ㅋ