Silver I 난이도 문제를 C++로 풀이한 내용입니다. 주어진 숫자들과 연산자 개수를 이용하여 만들 수 있는 식의 최댓값과 최솟값을 찾는 문제입니다.

백준 14888: 연산자 끼워넣기

Silver I 난이도 문제를 C++로 풀이한 내용입니다. 주어진 숫자들과 연산자 개수를 이용하여 만들 수 있는 식의 최댓값과 최솟값을 찾는 문제입니다.

문제 소개

문제 번호: 14888
문제명: 연산자 끼워넣기
난이도 (티어): Silver I
사용 언어: C++
실행 시간: 0 ms
메모리: 2020 KB
문제 요약: N개의 숫자가 주어지고, 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수가 주어집니다. 주어진 숫자 순서를 그대로 유지하면서 연산자를 끼워 넣어 만들 수 있는 모든 식의 결과 중 최댓값과 최솟값을 구하는 문제입니다.

접근 방법

문제를 처음 접했을 때, N개의 숫자를 나열하고 그 사이에 연산자를 끼워 넣는 모든 경우의 수를 탐색해야 한다는 점을 파악했습니다. 연산자의 개수가 제한적이고, 숫자의 순서는 고정되어 있기 때문에, 이는 백트래킹(Backtracking)으로 접근하는 것이 적합하다고 판단했습니다.

알고리즘/자료구조: 백트래킹(재귀 함수), 벡터
선택 이유:
- 백트래킹: 가능한 모든 조합을 탐색해야 하므로, 재귀 호출을 통해 각 단계에서 가능한 연산을 선택하고, 그 결과로 다음 단계를 진행하는 백트래킹 방식이 효과적입니다.
- 벡터: 숫자와 연산자 개수를 저장하고 관리하기 위해 벡터를 사용했습니다.

풀이 과정

입력 처리:
- 숫자의 개수 N을 입력받습니다.
- N개의 숫자를 a 벡터에 저장합니다.
- 덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수를 각각 o[1], o[2], o[3], o[4]에 저장합니다. (인덱스 1부터 4까지 사용)
초기값 설정:
- 첫 번째 숫자를 result 변수에 할당하여 연산의 시작점으로 삼습니다.
- 최댓값 max_res를 매우 작은 값(-1e9)으로, 최솟값 min_res를 매우 큰 값(1e9)으로 초기화합니다.
백트래킹 함수 backtrack(depth):
- 기저 조건: depth가 N에 도달하면, 모든 숫자에 대한 연산이 완료된 것이므로 min_res와 max_res를 현재 result와 비교하여 갱신하고 함수를 종료합니다.
- 재귀 단계:
  - 1부터 4까지 각 연산자에 대해 반복합니다.
  - 해당 연산자(o[i])가 아직 남아 있는지(o[i] > 0) 확인합니다.
  - 만약 연산자가 남아 있다면:
    - 현재 result 값을 tmp에 임시 저장합니다 (백트래킹 시 복구하기 위함).
    - 현재 result에 a[depth] (다음 숫자)를 적용하여 연산합니다.
    - 해당 연산자의 사용 횟수를 1 감소시킵니다 (o[i]--).
    - backtrack(depth + 1)을 호출하여 다음 단계로 진행합니다.
    - 되돌리기 (Backtracking):
      - 재귀 호출이 끝난 후, result 값을 원래대로 복구합니다.
      - 덧셈, 뺄셈, 곱셈은 역연산을 수행하여 복구합니다.
      - 나눗셈의 경우, result /= a[depth]를 수행했으므로 result = tmp로 복구해야 합니다 (나눗셈의 특성상 정확한 역연산이 어려울 수 있기 때문).
      - 사용한 연산자의 횟수를 1 증가시킵니다 (o[i]++).
결과 출력:
- backtrack(1)을 호출하여 백트래킹을 시작합니다. (첫 번째 숫자는 이미 result에 있으므로 두 번째 숫자부터 연산 시작)
- 모든 탐색이 완료된 후, max_res와 min_res를 출력합니다.

코드 설명

#include<bits/stdc++.h>
using namespace std;

vector<int> a(11); // N개의 숫자를 저장할 벡터 (최대 11개까지 고려)
vector<int> o(5); // 연산자 개수를 저장할 벡터 (인덱스 1: +, 2: -, 3: *, 4: /)
int N, result, tmp, min_res = 1e9, max_res = -1e9; // N, 현재 결과, 임시 결과, 최솟값, 최댓값

// depth: 현재 처리 중인 숫자의 인덱스 (0부터 시작하지만, backtrack 함수 호출 시 1부터 시작)
void backtrack(int depth) {
    if(depth == N) { // depth 1~N-1까지 N-1개의 연산 완료. N에서 결과 출력
        min_res = min(min_res, result); // 현재 결과와 최솟값 비교하여 갱신
        max_res = max(max_res, result); // 현재 결과와 최댓값 비교하여 갱신
        return; // 기저 조건 도달, 함수 종료
    }

    for(int i = 1; i <= 4; i++) { // 1: +, 2: -, 3: *, 4: /
        if(o[i] > 0) { // 해당 연산자가 남아 있는지 확인
            int tmp = result; // 현재 result 값을 임시 저장 (백트래킹 복구를 위해)

            // 연산 수행
            if(i == 1)
                result += a[depth]; // 덧셈
            else if(i == 2)
                result -= a[depth]; // 뺄셈
            else if(i == 3)
                result *= a[depth]; // 곱셈
            else if(i == 4)
                result /= a[depth]; // 나눗셈 (정수 나눗셈)
             
            // 선택: 해당 연산자 사용 횟수 감소
            o[i]--;
            
            // 재귀 호출: 다음 숫자에 대해 연산 진행 (depth + 1)
            backtrack(depth+1); 
            
            // 되돌리기 (Backtracking)
            if(i == 1)
                result -= a[depth]; // 덧셈의 역연산: 뺄셈
            else if(i == 2)
                result += a[depth]; // 뺄셈의 역연산: 덧셈
            else if(i == 3)
                result /= a[depth]; // 곱셈의 역연산: 나눗셈
            else if(i == 4) // 나머지는 나누면서 사라져서 그냥 tmp로 되돌림
                result = tmp; // 나눗셈의 경우, tmp 값으로 result 복구
            
            // 선택 취소: 해당 연산자 사용 횟수 복구
            o[i]++;
        }
    }
}

int main(){
    // cin, cout 속도 향상 (필요시 사용)
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N; // 숫자 개수 입력

    for(int i = 0; i < N; i++)
        cin >> a[i]; // 숫자들 입력

    for(int i = 1; i <= 4; i++)
        cin >> o[i]; // 연산자 개수 입력 (1: +, 2: -, 3: *, 4: /)
    
    result = a[0]; // 첫 번째 숫자로 결과 초기화
    backtrack(1); // 두 번째 숫자부터 연산 시작 (depth = 1)
    
    cout << max_res << '\n' << min_res; // 최댓값과 최솟값 출력
    return 0;
}

복잡도 분석

시간 복잡도:
- 각 숫자(N-1개)에 대해 4가지 연산자 중 하나를 선택하는 문제입니다.
- 연산자 개수가 제한되어 있기 때문에, 정확한 시간 복잡도는 O(P(N, k1, k2, k3, k4) * N) 와 같이 표현될 수 있습니다. 여기서 P는 순열 조합을 의미하고, k는 각 연산자의 개수입니다.
- 백트래킹 과정에서 각 깊이마다 최대 4번의 재귀 호출이 발생하며, 총 N 깊이까지 탐색하므로, 최악의 경우 O(4^N)에 비례하는 시간 복잡도를 가질 수 있습니다. 하지만 연산자 개수에 따라 실제 탐색하는 경로는 줄어듭니다.
공간 복잡도:
- a 벡터와 o 벡터에 O(N)의 공간을 사용합니다.
- 재귀 호출 스택 깊이가 N이므로, O(N)의 공간을 사용합니다.
- 따라서 전체 공간 복잡도는 O(N)입니다.

배운 점

이 문제를 통해 백트래킹 알고리즘의 기본 원리를 다시 한번 익힐 수 있었습니다. 특히, 재귀 호출 시 상태를 임시 저장하고, 재귀가 끝난 후 원래 상태로 복구하는 '되돌리기' 과정의 중요성을 체감했습니다. 또한, 나눗셈 연산의 경우 정수 나눗셈으로 인해 결과가 달라질 수 있으므로, 역연산을 수행할 때 주의해야 함을 알게 되었습니다. 문제의 제약 조건(숫자 순서 고정, 연산자 개수 제한)을 파악하여 효율적인 탐색 방법을 선택하는 연습이 되었습니다.