백준 16637 괄호 추가하기

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

16637번: 괄호 추가하기

#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
#include<string.h>
#define NSIZE 19
using namespace std;
char input[NSIZE];
int chk[NSIZE];
int N;
int Max = 0x80000000;
int sum(int idx) {
    int num = 0;
    if (input[idx] == '*') {
        num = (input[idx - 1] - '0') * (input[idx + 1] - '0');
    }
    if (input[idx] == '-') {
        num = (input[idx - 1] - '0') - (input[idx + 1] - '0');
    }
    if (input[idx] == '+') {
        num = (input[idx - 1] - '0') + (input[idx + 1] - '0');
    }
    return num;
}
void dfs(int idx,int answer) {
    if (idx>=N) {
        Max = Max < answer ? answer : Max;
        return;
    }
    int num = 0;
    //괄호 안하고
    if (input[idx] == '+') {
        num = answer + (input[idx+1] - '0');
    }
    else if (input[idx] == '-') {
    num = answer - (input[idx+1] - '0');
 
    }
    else if (input[idx] == '*') {
    num = answer * (input[idx+1] - '0');
 
    }
    dfs(idx+2, num);
 
    if (idx+2 < N) {
        //괄호 하고 
        if (input[idx] == '+') {
                num = answer + sum(idx+2);
        }
        else if (input[idx] == '-') {
                num = answer - sum(idx +2);
        }
        else if (input[idx] == '*') {
                num = answer * sum(idx + 2);
        }
        dfs(idx + 4, num);
    }
}
void init() {
    scanf("%d", &N);
    scanf("%s", input);
}
int main(void) {
    init();
    if (N == 1) {
        printf("%c", input[0]);
        return 0;
    }
    dfs(1,input[0]-'0');
    printf("%d", Max);
 
}

이번문제는 쉽긴했는데 생각하는 과정이 조금 어려웠네요. 

지금까지 풀었던 문제와는 조금 다르게 인덱스를 0 부터 시작이아니고 1부터 시작하고 , 값을 처음 넘긴다음에 

구현해야합니다. 

그래야 8 * 9 + 0  이 입력이라면 

우선 * 를 기준으로 그 뒤에 오는 숫자만 잘 계산해주면 간단해 지기 때문이죠.

물론 경우를 뽑고 계산을 해도되지만 솔직히 이런문제는 계산을 미리 할수 있으면 계산을 하고 넘기는게 

어쩔때는 4배이상 빠른것같아요.

대신 여기서 포인트는

 

이렇게 나눠서 구현만 잘해주면 재귀는 알아서 해줍니다. 약간 네비찍으면 알아서가는 자동차 같은 느낌 아닌가 하네요.

재귀는 이럴때 정말 편해요.

다들 익숙해져봐요.

오늘은 여기까지이고 의문이있는점은 댓글 달아주세요.