[C] Backjoon 16637 괄호 추가하기

백준 16637번 문제는 괄호 추가하기이다. 문제에 대한 내용과 그림 등은 백준에서 직접 확인하길 바란다. 복잡하지 않은 알고리즘 문제에서는 바로 코딩을 해도 되지만, 문제를 분석하고 어떤 함수와 요소들을 활용하여 문제를 해결할지 고민하고 정리하는 것이 시행착오를 줄일 수 있다.

문제 요구 사항을 분석하면 아래와 같다.

1. 3가지 연산기호에 대한 연산
2. 괄호 추가를 통한 연산 우선순위 변경 기능 구현
3. 연산 결과를 비교하여 최대값을 저장 및 반환

문제 상세 요건 및 분석사항은 아래와 같다.

1. 괄호는 중첩되면 안된다.
2. 정수와 연산자가 번갈아가면서 제공되어 전체 길이는 홀수이다.
3. 수식의 길이범위 제한 (<=19), 정수의 크기제한 (0~9)

문제의 해결 방향은 DFS 함수로 작성한 (실제로 DFS는 아니지만) 재귀호출 구현 함수를 통해 괄호 연산을 수행한 경우와 아닌 경우를 분별해 수식을 계산해 나간다. 이번 문제는 간단하지만 이동 인덱스 처리에 유의해야하는 문제이다. 또한 이 문제 해결시 작은 팁은 최소값의 초기화를 0으로 하면 계산 결과가 음수값이 최대값인 경우를 무시하게 되므로 충분히 작은 수로 최소화를 해주어야 한다.

#include <stdio.h>

int a_num[10];
char oper[10];
int out_val=-99999999;

int calculate(int a, int b, char c){
    int cal=0;
    switch (c){
        case '+' : cal=a+b; break;
        case  '-': cal=a-b; break;
        case '*' : cal=a*b; break;
    }
    return cal; 
}


void DFS(int idx, int N, int prev_val, char t_oper){
    int temp=0;
    if (idx==0){
        temp = calculate(a_num[idx] , a_num[idx+1] , oper[idx]);
        DFS(idx+2, N, calculate( 0, temp, '+'), oper[idx+1]);
        
        DFS(idx+1, N, calculate( 0, a_num[idx], '+'), oper[idx]);        
    }

    if (idx > N/2){
        if (prev_val > out_val) out_val = prev_val; 
        return;
    }

    if (idx > 0 && idx < N/2 ){
        temp = calculate(a_num[idx] , a_num[idx+1] , oper[idx]);
        DFS(idx+2, N, calculate(prev_val, temp, t_oper), oper[idx+1]);
    }
    
    DFS(idx+1, N, calculate(prev_val, a_num[idx], t_oper), oper[idx]);
}

int main(){
    int N;
    scanf("%d", &N);

    for (int i=0; i< N/2; i++){
        scanf("%d", &a_num[i]);
        scanf("%c", &oper[i]);
    }
    scanf("%d",&a_num[N/2]);

    DFS(0, N, 0, '+');
    printf("%d", out_val);

    return 0; 
}