[백준/C언어] 14888번 - 연산자 끼워넣기

백준 웹사이트 "14888번 - 연산자 끼워넣기" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

14888번: 연산자 끼워넣기

---

소스 코드

#include <stdio.h>

void solve(int count, int N, int add, int sub, int mult, int div, int value);

//global variables
int max = -1000000000;
int min = 1000000000;
int num[11];

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

    solve(0, N, operators[0], operators[1], operators[2], operators[3], num[0]);
    printf("%d\n", max);
    printf("%d\n", min);
}

void solve(int count, int N, int add, int sub, int mult, int div, int value){
    if(count==N-1){ //남은 연산자의 개수: 0
        //value가 최종 value -> max, min과 비교
        if(value>max)
            max = value;
        if(value<min)
            min = value;
    }
    else{
        //남은 연산자의 개수: N-1-count
        if(add!=0){
            solve(count+1, N, add-1, sub, mult, div, value + num[count+1]);
        }
        if(sub!=0){
            solve(count+1, N, add, sub-1, mult, div, value - num[count+1]);
        }
        if(mult!=0){
            solve(count+1, N, add, sub, mult-1, div, value * num[count+1]);
        }
        if(num[count+1]!=0 && div!=0){
            solve(count+1, N, add, sub, mult, div-1, value / num[count+1]);
        }
    }
}

---

문제 풀이

  이 문제는 global variable(전역 변수)를 이용하는 것이 가장 쉽습니다. N개의 수로 이루어진 수열 'num'을 global variable로 지정하면, main 함수와 solve 재귀함수 모두 이에 쉽게 접근이 가능합니다. 또한, 최대와 최소 수식 결과를 기록하는 변수 'min'과 'max'도 전역 변수로 선언함으로써 쉽게 접근할 수 있습니다.

  'solve' 재귀함수는 다음과 같이 정의합니다.

함수: solve(int count, int N, int add, int sub, int mult, int div, int value)

파라미터
- count : 재귀 반복 횟수
- N : 수의 개수 (2≤N≤11)
- add : 덧셈의 개수
- sub : 뺄셈의 개수
- mult : 곱셈의 개수
- div : 나눗셈의 개수
- value : 현재까지 수식의 값

Base Case (기본 케이스)
- 조건문: count == N-1
- 실행문: value를 min, max와 비교하여 최대/최소라면 알맞게 바꿔줌

Recursive Case (재귀 케이스)
- 조건문: count != N-1 (count가 N-1보다 작을 경우)
- 실행문: 덧셈/뺄셈/곱셈/나눗셈이 남아있다면, 이를 적용시키고 재귀
- 재귀
     add!=0이면, solve(count+1, N, add-1, sub, mult, div, value + num[count+1])
     sub!=0이면, solve(count+1, N, add, sub-1, mult, div, value - num[count+1])
     mult!=0이면, solve(count+1, N, add, sub, mult-1, div, value * num[count+1])
     div!=0이면, solve(count+1, N, add, sub, mult, div-1, value / num[count+1])

 

  solve 재귀함수의 Recursive Case (재귀 케이스)를 봅시다. 한 번의 재귀가 일어날 때마다, 덧셈/뺄셈/곱셈/나눗셈 중 하나의 연산자를 선택하여 적용시킵니다. 이때 식의 계산은 연산자의 우선 순위를 무시하고 앞에서부터 계산하므로, 연산자를 선택함과 동시에 값에 적용시켜도 괜찮습니다. 이렇게 N-1개의 연산자를 모두 배치시키면 N-1번째 재귀에서 Base Case (기본 케이스)로 넘어갑니다.

  Base Case (기본 케이스)를 들어오게 되면, 그때의 value 값은 이미 최종 수식의 값입니다. 이를 최대/최소와 비교하여 만약 최대/최소라면 새롭게 바꿉니다. 백트래킹의 특성 상, 가능한 모든 수식들의 값을 확인하게 됩니다. 따라서 최종 max/min은 가능한 모든 수식 중 최대/최소를 가지게 됩니다.