Home BOJ - 1541 - 잃어버린 괄호
Post
Cancel

BOJ - 1541 - 잃어버린 괄호

BOJ - 1541 - 잃어버린 괄호

문제


1541번: 잃어버린 괄호

문제 개념


문제

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

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

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

입력

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

출력

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

구현


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>

using namespace std;

// 주어진 식에서 괄호를 치는 행위를 통해 최솟값을 구하여라 
// 1. 순서는 바뀔 수 없으며 오로지 괄호를 이용한다. 
// 2. (-)가 존재하면 (+)끼리 묶어 먼저 계산한다. 

int main()
{
    // 식 입력 받기 
    string str;
    cin >> str;
    vector<int> iv;
    vector<char> ic;
    string temp = "";
    for(int i=0; i <= str.size(); i++)
    {

        if(str[i] == '-' || str[i] == '+' || i == str.size())
        {
            iv.push_back(stoi(temp));
            temp = "";
            ic.push_back(str[i]);
            
        }
        else
            temp += str[i];
    }
    // 양의 부호를 가지면 묶는다. 
    for(int i=0; i < ic.size(); i++)
    {
        if(ic[i] == '+')
        {
            iv[i] += iv[i+1];
            iv.erase(iv.begin() + i+1);
            ic.erase(ic.begin() + i);
            i--;
        }
    }
    // 이후 음의 부호를 가지는 것들을 해결한다.
    for(int i=0; i < ic.size(); i++)
    {
        if(ic[i] == '-')
        {
            iv[i] -= iv[i+1];
            iv.erase(iv.begin() + i+1);
            ic.erase(ic.begin() + i);
            i--;
        }
    }
    int answer = iv[0];
    cout << answer << endl;
    return 0;
}

SOL


  • ( + )인 경우들을 먼저 묶어 계산 후 ( - )를 처리한다.

Reference & 다른 PS 모음집


GitHub - ggh-png/PS: 2021.01.11 start

This post is licensed under CC BY 4.0 by the author.