[BOJ] #14888 : 연산자 끼워넣기

문제링크

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

예제 입력1

입력

2
5 6
0 0 1 0

출력

30
30

예제 입력2

입력

3
3 4 5
1 0 1 0

출력

35
17

예제 입력3

입력

6
1 2 3 4 5 6
2 1 1 1

출력

54
-24

📝 첫 번째 로직

원래는 본격적인 알고리즘을 공부하기 전에 몸풀기겸 연습용으로 이 문제를 접하게 되었다. (한참 후에 이 문제가 백트래킹, 브루트포스 문제인 것을 확인했다..😅)

문제를 처음 읽자마자 생각난 로직은

"연산자의 모든 순열을 나열해서 하나하나 계산을 하자!" 

였다.

그렇다면 순열은 어떻게 구할 것인가?를 생각했고,
참 바보같이 재귀로 구하는 방법말고 next_permutation 함수가 떠올랐다..😅

STL에 algorithm 헤더파일을 추가하면 다음 아래 함수를 통해서 순열을 구할수가 있다.

함수에 벡터의 iterator 혹은 배열의 주소를 넣으면 다음 순열(1-2-3-4의 다음 순열은 1-2-4-3) 혹은 이전 순열(1-2-4-3의 이전 순열은 1-2-3-4)의 결과가 벡터나 배열에 적용된다.

next_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구하고 true를 반환한다. 다음 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 작다면) false를 반환.

prev_permutation: 현재 나와 있는 수열에서 인자로 넘어간 범위에 해당하는 이전 순열을 구하고 true를 반환한다. 이전 순열이 없다면(다음에 나온 순열이 순서상 이전 순열보다 크다면) false를 반환.

출처 : https://twpower.github.io/82-next_permutation-and-prev_permutation

로직 설명

1. 셋째 줄에 입력받은 연산자들의 개수에 따라 인덱스 번호를 나열한다. ('+'는 0, '-'는 1, '*'는 2, '/'는 3)

2. 나열한 값들로 next_permutation을 이용하여 순열을 구한다.

2-1. 순열 하나를 구할 때마다 해당 순서에 맞게 계산한다.

2-2. min, max를 비교하여 갱신한다.

코드

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int maxResult=-999999999, minResult=999999999;

int calculate(int totalOperators, int onePermuations[], int inputValue[]){
    int total=inputValue[0];
    
	/* step 2-1. */
    
    for(int i=0;i<totalOperators;i++){
       
        if(onePermuations[i]==0){
            total=total+inputValue[i+1];
        }else if(onePermuations[i]==1){
            total=total-inputValue[i+1];
        }else if(onePermuations[i]==2){
            total=total*inputValue[i+1];
        }else if(onePermuations[i]==3){
            if(total<0){
                total*=-1;
                total=(int)(total/inputValue[i+1]);
                total*=-1;
            }
            else total=(int)(total/inputValue[i+1]);
        }
        
    }
  	/* step 2-2. */
    if(total > maxResult) maxResult=total;
    if(total < minResult) minResult=total;

    return 0;
}

int makePermuations (int totalOperators, int operators[], int inputValue[]){
	/* step 1. */
    vector <int> v;
    int onePermutation[totalOperators];
    for(int i=0;i<4;i++){
        for(int j=0;j<operators[i];j++)
        v.push_back(i);
    }
	/* step 2. */
    do{
        for(int i=0;i<totalOperators;i++){
            onePermutation[i]=v[i];
        }
        calculate(totalOperators, onePermutation, inputValue);
    }while(next_permutation(v.begin(), v.end()));

    return 0;
}

int main(){
    int n, a[11], operators[4];
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=0;i<4;i++){
        scanf("%d",&operators[i]);
    }

    makePermuations(n-1, operators, a);

    printf("%d\n%d", maxResult, minResult);
}

❌코드 짜면서 한 실수❌

1. 입력 범위를 제대로 체크하지 않았다.
   (정말 이건,,, 정신 안 차리고 풀었다는 증거다...ㅜㅜ)
   main 부분에서 변수를 선언할 때 배열의 크기를 지정해줘야 하는데 아무 생각 없이

   a[10], operators[3]

   이렇게 선언을 했었다.
   이거 때문에 거의 몇 십분을 삽질했,,,,ㅠㅠ
   심지어 친구가 실수를 잡아줬다,,,,,
   할많안하^^

2. min,max를 비교할 때 if 문을 잘못썼다.
   최소값과 최대값이 아예 상반되는 개념이라서 동시에 두 값을 갱신하는 케이스를 생각하지 못했었다. 다시 말해서 처음 코드를 짰을 때는

   if(total > maxResult) maxResult=total;
   else if(total < minResult) minResult=total;

   이렇게 최소값과 최대값을 갱신하는 케이스를 아예 분리 시켰었다.
   만약에 maxResult < total < minResult 와 같은 상황에서는 maxResult와 minResult를 total로 모두 갱신시켜야 하기 때문에, else if로 분리시키면 안 되는 것이다.

이것도 친구가 알려준 사실,,,,^^

📝 두 번째 로직

첫 번째 로직으로 채점을 해보니,,, 웁스,, 코드 길이가 1659B였다,, 허허,,,,
게다가 첫 번째 로직은 내장 함수 (next_permutation)를 쓴 것이기 때문에 문제 의도와 벗어나기도 해서,
이번엔 재귀함수를 이용해서 코드를 다시 짜보자!하고 두 번째 로직을 세웠다.

로직 설명

1. 임의의 0으로 초기화 된 연산자 개수만큼의 빈 배열을 만든다. 
(이 배열은 현재 내가 사용하고 있는 연산자의 정보를 나타내는 배열이다. 
예를 들어서 [1,0,1,0] 이면 현재 나는 더하기 하나와 곱하기 하나를 썼다는 뜻이고, 
이 배열에 값을 더해나가는 순서가 연산자가 놓인 위치이다.
만약, [1.0,0,0] 후에 [1,0,1,0] 으로 배열 값이 바꼈다면 더하기를 먼저 사용하고, 그 후에 곱하기를 사용했다는 뜻이다.

2. 1.에서 만든 배열에 반복문을 돌리면서 배열값을 증가시키며 재귀함수를 호출하는데, 연산자 배열과 비교하면서 호출한다.
( 특정 인덱스에 대해 1.에서 만든 임의의 배열값과 연산자 배열값이 같다는 것은 해당 인덱스에 매칭되는 연산자를 다 썼다는 뜻이다.)

2-1. 재귀함수를 호출 할 때 현재 내가 사용한 연산자의 개수, 현재까지의 연산결과, 현재까지의 임의 배열 값들을 넘기면서 호출한다.

2-1-1. 연산을 할 때는 연산 함수를 부르는 시점을 기준으로 방금 사용한 연산자 (실제로는 연산자와 매칭되는 인덱스 값)와, 피연산자, 이때까지의 연산결과를 가지고 진행한다.  
3. 주어진 모든 연산자를 썼으면, 완성된 합계를 가지고 최대값과 최소값을 비교하여 갱신한다.

코드

#include<stdio.h>
using namespace std;

int n, a[11], operators[4];
int maxResult=-999999999, minResult=999999999;

int calculate(int operatorIndex, int operand, int sum){
    if(operatorIndex==0){
        return sum+operand;
    }else if(operatorIndex==1){
        return sum-operand;
    }else if(operatorIndex==2){
        return sum*operand;
    }else {
        return (int)(sum/operand);
    }
}
void makeOper(int i, int sum, int temp[]){
    
    if(i==n-1){
        if(sum>maxResult) maxResult=sum;
        if(sum<minResult) minResult=sum;
        return;
    }

    for(int j=0;j<4;j++){
      if(temp[j]<operators[j]){
          temp[j]++;
          makeOper(i+1, calculate(j,a[i+1],sum), temp);
          temp[j]--;
      }
    }
    
}

int main(){
    /*input*/
    
    scanf("%d",&n);

    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    for(int i=0;i<4;i++){
        scanf("%d",&operators[i]);
    }

    int temp[4]={0};
    makeOper(0, a[0], temp);

    printf("%d\n%d", maxResult, minResult);
}

❗ 코드 짜면서 놓친점 ❗

1. return 된 후, 방금 사용한 배열 풀어주기
   위 코드에서 makeOper 재귀를 부른 다음 줄에

   a[10], operators[3]

   라는 구문이 있는데, 이건 제목에서 말했듯이 방금 사용한 배열을 풀어준다는 뜻이다.
   재귀함수를 호출할 때마다 갱신된 temp 배열을 가지고 다니기 때문에 리턴되어 다시 돌아왔을 때, 원래 상태로 배열을 돌려놔야 한다.
   그렇지 않으면 [0,0,0,0]에서 시작해서 처음으로 모든 연산자를 다 사용한 순간에 코드가 끝나버린다.
   그림으로 설명하자면,
   
   위에서부터 시작해서 아래로 내려오다가 연산자 배열과 값이 모두 같으니 ([2,1,1,1]) 리턴되어 배열값이 원래 상태([2,1,1,0])로 돌아가야 하는데 ([2,1,1,1]) 인 상태로 남아있는 채 리턴된다는 뜻이다.

⭐ 정리

1 . 입력조건 잘 체크하기
2. if문 쓸 때 else는 신중히 고려해서 쓰기
3. 재귀함수 return시, 어떤 상태로 돌아가야 하는지 로직 분명히 세우기