14888번: 연산자 끼워넣기(백준 C++)

14888번: 연산자 끼워넣기 링크

코드

#include <iostream>
#include <climits>
using namespace std;

int oper[4] = {0, }; // + - * /
int num[100];

int n;

int max_num = INT_MIN;
int min_num = INT_MAX;

void solve(int cnt, int now){
    if(cnt == n){
        max_num = now > max_num ? now : max_num;
        min_num = now < min_num ? now : min_num;
    }
    else{
        for(int j=0; j<4; j++){
            if(oper[j] == 0) continue;
            else{
                int temp = now;
                if(j == 0) now += num[cnt];
                else if(j == 1) now -= num[cnt];
                else if(j == 2) now *= num[cnt];
                else if(j == 3) now /= num[cnt];
                oper[j] -= 1;
                solve(cnt+1, now);
                oper[j] += 1;
                now = temp;
            }
        }
    }
}

int main() {
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> num[i];
    }
    for(int j=0; j<4; j++){
        cin >> oper[j];
    }
    solve(1, num[0]);
    cout << max_num << endl << min_num;
    return 0;
}

풀이 및 사견

단계별 문제풀이에서 백트래킹을 풀 수록 약간 느껴지는게 있다.
백트래킹류 문제 풀이를 할 때 가장 중요하게 생각해야 하는 것 두 가지.

1. 재귀 종료 조건
2. 반복문의 간소화

나의 이번 문제에 대한 재귀 종료 조건

if(cnt == n){
        max_num = now > max_num ? now : max_num;
        min_num = now < min_num ? now : min_num;
    }

cnt는 연산에 사용된 연산자의 개수이다.
문제에서 N개의 수와 N-1개의 연산자를 사용하여 최대값과 최소값을 구하라 하였으므로
연산자의 사용 수가 N개째, 즉 주어진 N-1개를 초과하여 사용하기 전에 재귀를 종료하는 것이다.

나의 이번 문제에 대한 반복

for(int j=0; j<4; j++){
            if(oper[j] == 0) continue;
            else{
                int temp = now;
                if(j == 0) now += num[cnt];
                else if(j == 1) now -= num[cnt];
                else if(j == 2) now *= num[cnt];
                else if(j == 3) now /= num[cnt];
                oper[j] -= 1;
                solve(cnt+1, now);
                oper[j] += 1;
                now = temp;
            }
        }

단순히 연산자들만 저장되어 있는 oper 배열에 대해서만 반복문을 돌려주고, 연산자 사용 개수는 재귀함수의 인자로 넘겨서 세었다. 백트래킹 문제 풀때 이중반복문으로 풀면 대개는 시간초과가 나는 듯 하다.

어제 엊그제 이보다 조금 어려운 난이도를 풀었더니 그래도 생각보다 할 만했다.
푸는데도 얼마 걸리지 않았고... 백트래킹에 대한 어느정도 감이 잡혀간다.