c언어 14888 연산자 끼워넣기 (백준)

14888번 : 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

내가 만든 코드

#include <stdio.h>

int num[12]; //입력받은 수
int n = 0;
int ao[5] = {0, }; //사칙연산 + - * / 순
int tmp = 0;
int max = -100000000; //처음에 반드시 바뀌게
int min = 100000000; //처음에 반드시 바뀌게

void find(int k)
{
    if(k==n-1) { //모든 연산자를 다 사용했으면
        max = (max>=tmp) ? max : tmp; //최댓값
        min = (min<=tmp) ? min : tmp; //최솟값
        return;
    }
    
    for(int i = 0; i<=3; i++) {//+ - * /  남은 연산자가 없을 때 까지 재귀
        if(ao[i] > 0 && i == 0) {
            tmp += num[k+1]; //tmp 에 num[k+1]+해줌
            ao[0]--; //+연산자 감소
            find(k+1); //깊숙히
            ao[0]++; //+연산자 다시 증가
            tmp -= num[k+1]; //tmp 에 num[k-1]+해줌
        } 
        if(ao[i] > 0 && i == 1) { //+처럼...
            tmp -= num[k+1];
            ao[1]--;
            find(k+1);
            ao[i]++;
            tmp += num[k+1];
        }
        if(ao[i] > 0 && i == 2) { //+처럼...
            tmp = tmp * num[k+1];  
            ao[2]--;
            find(k+1);
            ao[2]++;
            tmp /= num[k+1];
        }
        if(ao[i] > 0 && i == 3) { 
            int tmp_tmp = tmp; //기존의 값을 따로 저장
            tmp = tmp / num[k+1]; //나눈다!
            ao[3]--; //나누기 연산자 감소
            find(k+1); //깊숙히
            ao[3]++; //나누기 연산자 증가
            tmp = tmp_tmp; //깊숙히 들어가지 전의 tmp값을 대입
        }
    }
}

int main(void)
{
    scanf("%d", &n);
    
    for(int i = 0; i<n; i++) scanf("%d", &num[i]); 
    tmp = num[0];
    
    scanf("%d %d %d %d", &ao[0], &ao[1], &ao[2], &ao[3]);
    
    
    find(0);
    
    printf("%d\n%d", max, min);
    
    return 0;
}

수와 연산자를 입력 받은 후, 재귀함수에서 연산자가 있으면 사칙연산을 한 후, 재귀

이를 계속 반복하다가, k == n-1, 즉 모든 연산자를 다 사용 했을 때 (연산자는 원래 n-1개 있으나, k=0부터 시작했으므로 k=n-1일 땐 모든 연산자가 0 이다.) 계속 계산해온 값을  max, min값과 비교함.

 

재귀에서 나와도 tmp값은 달라졌기에, k+1되기전의 tmp값을 대입

 

c언어는 음수 / 양수 에서 몫은 음수를 양수로 바꾼 뒤 구해진 몫에 -1을 곲한 것으로 나오기 때문에 별다른 조치를 취하진 않았다.

ex) -7 / 2 : 몫_-3,    나머지_-1