1541번 잃어버린 괄호 BOJ 백준 C언어

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

출력

첫째 줄에 정답을 출력한다.

구현

최소값을 만들기 위해서는 +로 되어있는 앞 뒤의 숫자를 모두 더해준후 제일 앞 수에서 빼주어야한다.

해당 문제의 경우 분기점으로 나눠야할 경우의 수가 총 3가지이다.

1. -가 왔을 경우
앞까지의 숫자들을 따로 더해서 새로운 배열에 추가해준다.

2. +가 왔을 경우

앞의 숫자를 sum 값에 저장해준다.

3. 숫자가 왔을 경우

숫자가 왔을 경우에는 문자열로 받았기 때문에 원래 값에 10을 곱해주고 1의 자리를 더해야한다.
이때

temp = temp + str[i] - '0';

를 해주는 이유는 문자열에서 '0' 을 빼줘야 숫자로 제대로 받아지기 때문이다.

4. 마지막으로 새로운 배열에 저장된 모든값을 처음 배열 값에서 빼준다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#define _CRT_SECURE_NO_WARNINGS

int main(void) {
    char str[51];
    int arr[25] = { 0 };
    scanf("%s", str);
    int len = strlen(str);
    int i, j = 0, k = 0, temp = 0, sum = 0, result = 0;

    for (i = 0; i <= len; i++) {
        if (str[i] == '-' || i==len) {
            sum = sum + temp;
            arr[j] = sum;
            j++;
            temp = 0;
            sum = 0;
        }
        else if (str[i] == '+') {
            sum = sum + temp;
            temp = 0;
        }
        else {
            temp = temp * 10;
            temp = temp + str[i] - '0';
        }
    }

    result = arr[0];
    for (i = 1; i < j; i++) {
        result = result - arr[i];
    }
    printf("%d", result);
}