[백 트래킹] BOJ 14888 연산자 끼워넣기

 

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

문제 해결 알고리즘

 

1. num(숫자들의 개수), v(숫자들을 입력받는 배열), c(연산자들을 입력받는 배열)에 입력을 받는다.

 

2. dfs함수를 실행한다.

 

이때, n과 num이 같으면 최대값과 최소값을 갱신해준다.

 

같지 않다면, 연산자들을 순서대로 계산한 값과 v에서의 인덱스를 dfs함수에 다시 넣어 실행해준다.

그 전에 c배열에서의 해당 연산자를 하나 빼주고, 함수를 실행한 후, 다시 더해준다.

(i값에 대해서 어떤 연산을 해야할지 각각 케이스를 나눠준다.)

 

그렇게 dfs 함수가 전부 다 실행된 후에, max_result와 min_result를 출력해준다.

 

소스 코드

 

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

int num;
vector<long long> v(11);
vector<long long> c(4);
long long max_result = -1000000001, min_result = 1000000001; 

void dfs(int n, long long result){
  if(n == num) {
    max_result = max(max_result, result);
    min_result = min(result, min_result);
    return;
  }

  for(int i=0;i<4;i++){
    if(c[i] == 0) continue;
    c[i]--;
    if(i == 0) dfs(n+1, result + v[n]);
    else if(i == 1) dfs(n+1, result - v[n]);
    else if(i == 2) dfs(n+1, result * v[n]);
    else dfs(n+1, result / v[n]);
    c[i]++;
  }

  

}

int main(){
  cin >> num;

  for(int i=0;i<num;i++) cin >> v[i];

  for(int i=0;i<4;i++) cin >> c[i];

  dfs(1,v[0]);

  cout << max_result << '\n' << min_result;
}

 

메모

 

이 문제에서도 Segmentation fault 오류가 났는데,

그 이유로는 v의 크기를 잡을 때, 입력 받지 않은 num으로 잡은 것 때문이었다. 입력 받지 않은 값을 벡터의 크기로 지정해주면  Segmentation fault 오류가 난다.