연산자 끼워넣기

문제: 연산자 끼워넣기 (백준 14888번)

구조 분석

해당 문제는 수학 문제처럼 보일 수 있으나 조건을 잘 살펴보면 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.라는 말이 있다. 즉, 이는 backtracking문제이며 이는 dfs를 이용해서 쉽게 풀 수 있다.

풀이 방법

해당 문제는 dfs를 이용해서 앞에서부터 연산을 수행하면 된다. DFS의 tree branch는 연산자이고, 배열에 저장된 수를 모두 탐색하면 min값과 max값을 업데이트 해주면 된다.

해당 문제에서 삽질한 부분은 초기 min값과 max값을 설정하는 부분이었는데, 문제에서 결과값의 범위가 -10억부터 10억까지라고 명시됨을 고려하여 초기 min값은 10억, 초기 max값은 -10억으로 설정한 후 dfs를 실시하면 모든 코너케이스에 대해 정답을 출력한다.

코드

#include <stdio.h>
#include <iostream>
#include <math.h>
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a>b?b:a)
using namespace std;

int n;
long long minNum=1000000000, maxNum=-1000000000;
long long A[11];
int op[4] = {0,}; // [#plus, #minus, #mul, #div]


void dfs(long long num, int level) {
    if (level == n) {
        minNum = MIN(minNum, num);
        maxNum = MAX(maxNum, num);
        return;
    }
    long long n1 = num;
    long long n2 = A[level];
    for (int i=0; i<4; i++) {
        long long tmpNum = 0;
        if (i==0 && op[i]>0) {
            tmpNum = n1 + n2;
            op[i]--;
            dfs(tmpNum, level+1);
            op[i]++;
        }
        else if (i==1 && op[i]>0) {
            tmpNum = n1 - n2;
            op[i]--;
            dfs(tmpNum, level+1);
            op[i]++;
        }
        else if (i==2 && op[i]>0) {
            tmpNum = n1 * n2;
            op[i]--;
            dfs(tmpNum, level+1);
            op[i]++;
        }
        else if (i==3 && op[i]>0) {
            if (n1 < 0) {
                int q = abs(n1) / n2;
                tmpNum = 0 - q;
            }
            else {
                tmpNum = n1 / n2;
            }
            op[i]--;
            dfs(tmpNum, level+1);
            op[i]++;
        }
    }
}

int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> A[i];
    }    
    for (int i=0; i<4; i++) {
        cin >> op[i];
    }
    dfs(A[0], 1);
    cout << maxNum << "\n" << minNum << "\n";
    return 0;
}

정리

해당 문제는 dfs를 이용한 간단한 문제였다.