[백준][C++] 1541: 잃어버린 괄호 (greedy)

문제

1541: 잃어버린 괄호

풀이

• 주어진 식에서 적절히 괄호를 쳐 최소값을 얻어내는 문제

• 이 문제는 분할 정복으로 해결할 수 있다.

• 그 이유는 식에 ‘+’, ‘-‘ 만 있기 때문이다.

• ’-‘ 기준으로 뒤에 있는 식을 양수 즉 ‘+’로만 이루어진 식만 있게해야한다.

• 그 이유는 최소가 되게하려면 음수를 많이 생성해야하기 때문이기 때문에 ‘-‘ 개수만큼 음수를 만들고 합치면 문제는 해결된다.

분할과 정복

• 분할은 간단하다 ‘-‘ 를 기준으로 앞 과 뒤를 나누고, ‘-‘인지 ‘+’인지를 넘겨주면된다.

• 아래 식은 - 기준으로 나눈것이다. 앞의 식은 이전의 부호를 따르고, 뒤의 식은 ‘-‘를 넘겨 음수임을 알려줘야한다.

• 기저조건 ‘+’로만 이루어진 식을 처리만하면된다.

sign * re(s.substr(0, idx), 1) + re(s.substr(idx + 1), -1)

식 계산하기

• ’+’로만 이루어진 식을 계산하기 위해서 문자열을 파싱해야한다.
• ’+’를 찾고, stoi함수를 이용하여 해결하였다.

int sum(string &s)
{
    int ret = 0;
    auto idx = string::npos;
    while (string::npos != (idx = s.find("+")))
    {
        ret += stoi(s.substr(0, idx));
        s = s.substr(idx + 1);
    }
    return ret + stoi(s);
}

코드

#include <iostream>
#include <string>
#include <cmath>
#include <vector>

using namespace std;

int sum(string &s)
{
    int ret = 0;
    auto idx = string::npos;
    while (string::npos != (idx = s.find("+")))
    {
        ret += stoi(s.substr(0, idx));
        s = s.substr(idx + 1);
    }
    return ret + stoi(s);
}

int re(string s, int sign)
{
    auto idx = s.find("-");
    if (idx == string::npos)
    {
        return sign * sum(s);
    }
    return sign * re(s.substr(0, idx), 1) + re(s.substr(idx + 1), -1);
}

int main()
{
    string s;
    cin >> s;
    cout << re(s, 1);
}