[BaekJoon/백준] 14888번

삼성 SW 기초역량문제라고 한다.

 

순열 느낌의 문제.

처음에는 3 3 2 4 같은 각각의 연산자가 여러 횟수의 경우에는, 한번 뽑고 지나치지 않도록 해줘야 되는 줄 알았는데

사실 0번째 +를 뽑던 1번째 +를 뽑던 결과는 똑같은 +를 뽑은 순열로 나열된다. 어차피 재귀로 돌아가므로 알아서 다른 경우의 수를 뽑아주게 되어있다. 괜한 걱정을 했다! 직접 돌려보니 그러지 않아도 된다는 이해가 되었다.

 

#include <stdio.h>
#include <stdlib.h>

int *p;
int *oper_order; // 연산자를 차례로 저장할 배열

int n;
int oper[4];
int min = 1000000001;
int max = -1000000001;

void save() {
    int result = p[0];
    for(int i = 1; i < n; i++) {
        switch(oper_order[i - 1]) {
            case 1:
                result += p[i];
                break;
            case 2:
                result -= p[i];
                break;
            case 3:
                result *= p[i];
                break;
            case 4:
                result /= p[i];
                break;
        }
    }
    
    if(min > result)
        min = result;
    if(max < result)
        max = result;
}
void op(int oper_iter) {
    
    int j;
    if(oper_iter == n - 1) {
        save();
        return;
    }
    
    for(j = 0; j < 4; j++) {
        
        if(oper[j] != 0) {
            oper_order[oper_iter] = j+1; // 덧셈1 뺄셈2 곱셉3 나눗셈4
            oper[j]--;
            
            op(oper_iter + 1);
            
            oper_order[oper_iter] = 0; // 여기선 어차피 돌고도니까 0초기화 안해줘도될거같긴함.
            oper[j]++;
        }
    }
}

int main() {
    int i;
    
    scanf("%d", &n);
    
    p = calloc(n, sizeof(int));
    oper_order = calloc(n - 1, sizeof(int));
    
    for(i = 0; i < n; i++) {
        scanf("%d", &p[i]);
    }
    
    for(i = 0; i < 4; i++) {
        scanf("%d", &oper[i]);
    }
    
    op(0);
    
    printf("%d\n%d", max, min);
    
}