[C] Algorithm : Backjoon 16637 괄호 추가하기

Baekjoon Problem 16637 is the addition of parentheses. Please check the details and pictures of the problem in Baekjonn. For uncomplicated algorithmic problems, it is possible to code the problem right away, but it is possible to reduce trial and error by analyzing the problem and thinking about which functions and elements to solve the problem and organizing it.

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

Analysis of the problem requirements is as follows.

Calculation for 3 operators
Implementation of operation priority change function by adding parentheses
Save and return the maximum value by comparing the operation result

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

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

The detailed requirements and analysis of the problem are as follows.

Parentheses must not overlap.
Integer and operator are provided alternately, so the total length is odd.
Restriction on length range of formula (<=19), value limit of integer (0~9)

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

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

The direction of solving the problem is to calculate the equation by discriminating between the case where the parenthesis operation is performed and the case where the parenthesis operation is not performed through the recursive call implementation function (though not actually DFS) written with the DFS function. This problem is simple, but it is a problem to be careful about handling moving indexes. In addition, in solving this problem, if the minimum value is initialized to 0, the calculation result ignores the case where the negative value is the maximum value, so it must be minimized to a sufficiently small number.

문제의 해결 방향은 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; 
}

[C] Algorithm : Backjoon 16637 괄호 추가하기

Written by Software-engineer