[BOJ] 16637 - 괄호 추가하기

문제 링크

삼성 대비 문제가 모두 그렇듯, 문제를 제대로 읽어야 하는 문제다. 문제를 풀면서 실수했던 점을 적어본다.

1. 문제를 잘못 읽고 괄호의 크기가 반드시 하나인 것을 모르고 알고리즘을 짰던 점
2. 재귀함수를 짤 때 범위를 헷갈려했던 점
3. atoi함수를 사용하여 구현했는데, char형을 주소를 넣어주는 형태로 atoi에 억지로 집어넣으니 \0이 없어서인지, 이상한 오류가 발생하여 이상한 값을 리턴하는 문제가 발생했다. 한 문자를 int로 변환하고자 한다면

    int atoi(char a){
        return a-'0';
    }
   

   이런 식으로 정확히 해당 값을 빼서 구현하는 방식을 사용해야 할 것 같다.

   또한 중간에 두자리 이상의 숫자가 등장하는 문자열의 변환은 그냥 따로 char배열을 선언하여 집어넣고 돌리던지.. 따로 파싱하여 넣어야 뒤탈이 없을 것 같다. 이 부분은 처음에 사용하고자 생각했을 때도 찜찜했던 부분이라.. 시험 볼 때는 혹시 찜찜한 방법은 꼭 사용하지 말기로 하자.

소스코드

#include <iostream>
#include <algorithm>
#include <string.h>
#include <limits>
#define NEG_INF -(1<<31)
using namespace std;

int n;
char str[25];

int _cal(int a, char op, int b) {
    switch (op) {
    case '*':
        return a * b;
    case '+':
        return a + b;
    case '-':
        return a - b;
    }
    return 0;
}

int cal(int a, char op, char b) {
    return _cal(a, op, b - '0');
}

int cal(int a, char op, int b) {
    return _cal(a, op, b);
}

int cal(char a, char op, char b) {
    return _cal(a - '0', op, b - '0');
}

int go(int now, int sum) {
    char op = str[now + 1];
    int rtn = NEG_INF;
    if (now + 5 < n) // a + ( b + c )까지 계산하고 보냄
        rtn = max(rtn, go(now + 4, cal(sum, op, cal(str[now + 2], str[now + 3], str[now + 4]))));
    else if (now + 4 < n) // a + ( b + c )까지 계산
        rtn = max(rtn, cal(sum, op, cal(str[now + 2], str[now + 3], str[now + 4])));
    if (now + 3 < n) // a + b까지 계산하고 보냄
        rtn = max(rtn, go(now + 2, cal(sum, op, str[now + 2])));
    else // a + b까지 계산
        rtn = max(rtn, cal(sum, op, str[now + 2]));
    return rtn;
}

int main(void) {
    scanf("%d", &n);
    scanf("%s", str);
    printf("%d", n == 1 ? str[0] - '0' : go(0, str[0] - '0'));
    return 0;
}