BOJ14888 연산자 끼워넣기

2017 하반기 삼성전자 기출문제 (2번)

1. 문제링크 : BOJ14888 연산자 끼워넣기

2. 문제요약
  - N개의 자연수 수열이 주어진다.
  - 수열의 사이에 끼워 넣을 수 있는 N-1개의 연산자가 주어짐
  - 연산자는 덧셈, 뺄셈, 곱셈, 나눗셈 으로만 이루어짐.

GOAL : 만들수 있는 식의 최대값과 최소값 구하기

EX) 1 2 3 4 가 주어짐 (N=4) , ( +, + , *) 가 주어짐 (N-1=3)
 경우의수
 (1) 1+2+3*4 = 15
 (2) 1+2*3+4 = 11
 (3) 1*2+3+4 = 9

경우의 수는 3!/2! 임으로 3개.
이때 최대값은 15 최소값은 9

3. 문제풀이
  - 수열의 순서는 바뀌지 않음으로 연산자의 순열의 경우의 수만 세주면됨
  - 가장 단순한 방법은 C++의 next_permutation을 이용해 연산자의 순열의 경우를 다 따져서 계산해보면 됨
 - DFS나 BFS를 이용하여 브루트 포스를 수행할 수도 있음.
 - DFS의 경우 연산자를 하나씩 정해가며 다음 단계로 진행하고 모두 진행했을 경우 이전단계로 돌아와 다른 연산자를 고르고 다음단계로 진행, 추후 마지막 단계에서 계산을 수행
 - BFS의 경우 각 노드별로 다른 연산자를 선택하고 큐에 넣은다음 다음단계로 진행하며 마지막 단계에서 계산을 수행

4. 소스코드 ( C )
- DFS 이용

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define PLUS 1
#define MINUS 2
#define MUL 3
#define DIV 4
int oper[13];
int su[13];
int num[5];
int max;
int min;
int n;
int k;

void dfs(int start){
    if(start==k){
        int temp=su[0];
        for(int i=1;i<n;i++){
            int op=i-1;
            if(oper[op]==PLUS)
                temp+=su[i];
            else if(oper[op]==MINUS)
                temp-=su[i];
            else if(oper[op]==MUL)
                temp*=su[i];
            else if(oper[op]==DIV)
                temp/=su[i];

            
        }
        if(temp>max)
            max=temp;
        if(temp<min)
            min=temp;
    }

    for(int i=1;i<=4;i++){
        if(num[i]>0){
            oper[start]=i;
            num[i]--;
            dfs(start+1);
            num[i]++;
        }
    }
}

int main(void){
    max=-2000000000;
    min=2000000000;
    scanf("%d",&n);
    k=n-1;
    for(int i=0;i<n;i++){
        scanf("%d",&su[i]);
    }
    for(int i=1;i<=4;i++){
        scanf("%d",&num[i]);
    }
    dfs(0);

    printf("%d\n%d\n",max,min);
    return 0;
}