[BOJ 14888] 연산자 끼워넣기

문제출처

https://www.acmicpc.net/problem/14888

 

문제풀이

 재귀함수를 이용한 완전탐색 문제입니다. n의 최대값이 11이므로 완전탐색이 가능하다고 판단되어 완전탐색으로 풀이하였습니다.

숫자 순서는 변하지 않고 연산자 우선순위도 적용되지 않기 때문에 현재까지 계산한 값과 연산자를 통한 계산을 해주면 되는 문제입니다. 처음에 최대값, 최소값을 0xfffffff으로 초기화 했는데 틀렸습니다가 나왔다. 문제를 잘 읽어보면 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 라는 문구를 보아 10억으로 초기화 해서 해결했습니다.

 저같은 실수를 하신 분들을 위해 반례 하나 적어두겠습니다.

5

100 100 100 100 10

0 0 4 0

 

소스코드

#include <iostream>
using namespace std;
int n, mx=-1000000000, mn=1000000000;
int a[100], oper[4];

void solve(int curSum, int depth) {
    if (depth == n) {
        mx = curSum > mx ? curSum : mx;
        mn = curSum > mn ? mn : curSum;
        return;
    }

    if (oper[0] > 0) {
        oper[0]--;
        solve(curSum + a[depth], depth+1);
        oper[0]++;
    }
    if (oper[1] > 0) {
        oper[1]--;
        solve(curSum - a[depth], depth+1);
        oper[1]++;
    }
    if (oper[2] > 0) {
        oper[2]--;
        solve(curSum * a[depth], depth+1);
        oper[2]++;
    }
    if (oper[3] > 0) {
        oper[3]--;
        solve(curSum / a[depth], depth+1);
        oper[3]++;
    }
}

void init() {
    cin>>n;
    for (int i=0; i<n; i++) cin>>a[i];
    for (int i=0; i<4; i++) cin>>oper[i];
    solve(a[0], 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    init();
    cout<<mx<<"\n"<<mn<<"\n";
    return 0;
}