[C++] 백준 14888 : 연산자 끼워넣기

#include <iostream>

int A[101] = {0}; // 수열
int cal[100] = {0}; // 연산자 순서 저장 1 : +, 2 : -, 3 : *, 4 : /

int N;
int plus, minus, multiple, division;
long long min = 9999999999, max = -9999999999;

void DFS(int p, int m, int mul, int div, int cnt){
  if(p == 0 && m == 0 && mul == 0 && div == 0){ // 연산자 다 쓴 경우
    int tmp = A[0];

    for(int i = 1; i <= N; i++){
      if(cal[i] == 1){
        tmp += A[i];
      } else if(cal[i] == 2){
        tmp -= A[i];
      } else if(cal[i] == 3){
        tmp *= A[i];
      } else if(cal[i] == 4){
        tmp /= A[i];
      }
    }

    if(tmp > max){
      max = tmp;
    }
    if(tmp < min){
      min = tmp;
    }

    return;
  }

  for(int i = 1; i <= 4; i++){ // 연산자 1~4
    if(i == 1 && p > 0){
      cal[cnt] = i;
      DFS(p-1, m, mul, div, cnt + 1); // + 수 감소
    } else if(i == 2 && m > 0){
      cal[cnt] = i;
      DFS(p, m-1, mul, div, cnt + 1); // - 수 감소
    } else if(i == 3 && mul > 0){
      cal[cnt] = i;
      DFS(p, m, mul-1, div, cnt + 1); // * 수 감소
    } else if(i == 4 && div > 0){
      cal[cnt] = i;
      DFS(p, m, mul, div-1, cnt + 1); // / 수 감소
    }
  }
}

int main(int argc, char** argv){
  scanf("%d", &N);
  
  for(int i=0; i<N; i++){
    scanf("%d", &A[i]);
  }

  scanf("%d %d %d %d", &plus, &minus, &multiple, &division);

  DFS(plus, minus, multiple, division, 1); // 연산자는 1부터 시작

  printf("%lld\n%lld", max, min); // 출력은 마지막

  return 0;
}

드디어 인터넷을 전혀 참고하지 않고 삼성 기출 문제를 풀 수 있었다!
물론 백트래킹으로 풀어야한다는 것은 너무 명백했고, 공부한 것을 바탕으로 응용해서 문제를 푼 것이긴 하지만 말이다.

• if와 else if 주의하기, if문 만족하면 else if문은 돌아가지 않는다.

• 첫 수는 A[0]부터 시작한다. 따라서 나머지 연산자는 cal[1]을 사용하고 A[1]과 계산한다. index를 맞추어서 계산해나간다.

• 다른 사람들의 풀이를 보면 plus, minus 이 모든 것을 각각 변수로 두지 않고 배열을 이용하여 훨씬 간결히 코드를 작성하였음을 확인할 수 있다. 앞으로는 oper[4] 이런식으로 따로 배열을 선언하도록 하자.

• 연산자의 개수가 없음을 조건으로 하는 것이 아닌 depth가 N-1임을 종료 조건으로도 둘 수 있다.