[백준/BOJ] 14888번 연산자 끼워넣기 C++

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

 

맞힌 코드

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

int n;
vector<int> numbers;
vector<int> operators(4);
    
int maxValue = -1000000000;
int minValue = 1000000000;

void dfs(int idx, int now){
    int next;
    if(idx == n){
        maxValue = max(maxValue, now);
        minValue = min(minValue, now);
        return;
    }
    
    for(int i=0; i<4; i++){
        if (operators[i]>0){
            operators[i]--;
            
            next = now;
            if(i==0){
                next += numbers[idx];
            }
            else if(i==1){
                next -= numbers[idx];
            }
            else if(i==2){
                next *= numbers[idx];
            }
            else if(i==3){
                next /= numbers[idx];
            }
            dfs(idx+1, next);
            operators[i]++;
        }
    }
}

int main(){
    cin >> n;
    numbers.resize(n);
    
    for(int i=0; i<n; i++){
        cin >> numbers[i];
    }
    
    for(int i=0; i<4; i++){
        cin >> operators[i];
    }
    
    dfs(1, numbers[0]);
    
    cout << maxValue << '\n';
    cout << minValue;
}

 

메모

함수 정의 코드 작성할 때 괄호 안에 매개변수 타입도 작성했는데 그거 쓰기 싫다고 냅다 함수 밖에만 매개변수 이름의 변수를 타입이랑 같이 선언했음... 이런 실수 하지 마.

 

 

GPT 설명

이 코드는 브루트포스 알고리즘을 사용한 코드입니다. 가능한 모든 경우의 수를 탐색하여 최댓값과 최솟값을 구합니다. 구체적으로는 백트래킹을 활용해 연산자들의 조합을 효율적으로 탐색하는 방식입니다.

왜 브루트포스인가?

1. 모든 경우의 수를 시도:
   • 주어진 연산자들을 각각 사용하여 가능한 모든 조합을 시도합니다.
   • NNN개의 숫자 사이에 N−1N-1N−1개의 연산자를 배치할 수 있는 모든 경우를 계산하기 때문에 완전탐색(브루트포스) 방식입니다.
2. 백트래킹을 통해 불필요한 연산을 줄임:
   • 이미 사용한 연산자는 다시 사용하지 않도록 하고, 연산이 끝나면 상태를 복구(undo)합니다.
   • 이는 브루트포스 방식이지만 효율적인 탐색을 위한 백트래킹 기법이 포함된 형태입니다.

시간 복잡도

브루트포스의 경우 가능한 연산자 순열의 개수에 따라 시간 복잡도가 결정됩니다.

• NNN개의 숫자 사이에 N−1N-1N−1개의 연산자가 있을 때, 최대 경우의 수는 (N−1)!(N-1)!(N−1)!입니다.
• 그러나 각 연산자의 개수가 제한되어 있으므로 실제 경우의 수는 이보다 적을 수 있습니다.

장점과 단점

• 장점:
  • 문제의 크기가 작을 경우 모든 경우의 수를 탐색하여 정확한 답을 구할 수 있습니다.
  • 구현이 비교적 간단하고 직관적입니다.
• 단점:
  • 입력 크기가 커지면 연산 시간이 급격히 증가합니다.
  • NNN이 커질수록 효율이 떨어지므로 큰 입력에 대해서는 다른 최적화된 알고리즘이 필요할 수 있습니다.

대안

문제를 해결할 때 더 큰 NNN을 처리해야 한다면 동적 프로그래밍(DP)이나 다른 최적화된 탐색 알고리즘을 고려할 수 있습니다. 하지만 현재 조건(최대 N=11N=11N=11)에서는 브루트포스+백트래킹이 충분히 효율적입니다.