백준 14888 (삼성 SW 역량평가 기출) - 연산자 끼워넣기

 이 포스팅은 삼성 GIST 모터 트랙 대비 과정에서 풀었던 기출 문제에 대한 글입니다. 모두 백준에 공개된 문제들만 있으며, SW Expert Academy에서만 다루는 문제들은 저작권 문제로 업로드 되지 않습니다.

---

1. 문제 내용

이 문제는 삼성 SW 역량 평가 17년 하반기 오후 2번으로 제출된 문제입니다.

문제 링크: https://www.acmicpc.net/problem/14888

문제 난이도: SILVER 1

2. 접근법

• 숫자 순서도 그대로고, 연산 순서도 우선 순위 무시. 즉, 주어진 개수의 연산자들을 나열하는 경우의 수 문제!
• 경우의 수이므로 백트래킹으로 쉽게 풀이 가능.
• 이전에 풀었던 스타트와 링크 문제와 유사. 비슷한 방법으로 백트래킹하는 재귀 함수와, 종료 조건 도달 시 구하고자 하는 것을 계산하는 함수로 쪼개서 풀기!

3. 풀이 코드

#include <iostream>
#include <climits>
#include <vector>
#include <cmath>

using namespace std;

int N;
vector<int> opers;
int nums[11];
int mx = -1000000001, mn = 1000000001;
int numsOfOpers[4] = {0, };

void calculateAndCompare() {
    int val = nums[0];
    for(int i = 0; i < N - 1; i++) {
        if(opers[i] == 0) val += nums[i + 1];
        else if(opers[i] == 1) val -= nums[i + 1];
        else if(opers[i] == 2) val *= nums[i + 1];
        else val /= nums[i + 1];
    }
    
    //compare
    mx = max(mx, val);
    mn = min(mn, val);
}

void solve(int step) {
    
    //term case
    if(step == N - 1) {
        calculateAndCompare();
        return ;
    }
    
    // avg case
    for(int i = 0; i < 4; i++) {
        if(numsOfOpers[i] > 0) {
            numsOfOpers[i] --;
            opers.push_back(i);
            solve(step + 1);
            opers.pop_back();
            numsOfOpers[i]++;
        }
    }
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        cin >> nums[i];
    }
    for(int i = 0; i < 4; i++) {
        cin >> numsOfOpers[i];
    }
    solve(0);
    cout << mx << '\n' << mn << '\n';
    return 0;
}

4. 중요 포인트

• 백트래킹 패턴만 외우고 있으면 쉽게 풀 수 있는 문제였음.