[백준] 1541번 : 잃어버린 괄호 - C++

 

 처음 이 문제를 접했을 때는 백트래킹 문제인 줄 알았다. 하지만 괄호 치는 경우의 수를 따진다음, 그 모든 경우의 수를 계산한 다음 min 값을 찾는 방식으로 백트래킹을 해야하는 줄 알았지만, 천천히 생각해보면, 뭔가 규칙만 찾으면, 간단한 풀이가 나올 것 같아서 천천히 봤더니, 그리디 문제임을 직감했다. 

 

 - 이후에 괄호가 쳐져 있어서 안의 수들이 모두 - 취급을 받는 것이 가장 최소인 것을 알게 됐다. 만약 - 괄호 안의 - 를 만나게 되면 두 번째 -가 나오기 전까지의 괄호를 닫아준다는 식으로 생각해보면, 굉장히 간단해진다.

 

 즉, - 이후의 값은 모두 음수로 치부해서 계산하면 그것이 최소 값이 되는 것이다.

 

#include <bits/stdc++.h>
using namespace std;

int tmp, ans;
int sign = 1;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string input;
    cin >> input;

    for (char c : input) {
        if (c == '+' || c == '-') {
            ans += tmp * sign;
            if (c == '-') sign = -1;
            tmp = 0;
        }
        else {
            tmp *= 10;
            tmp += c - '0';
        }
    }
    ans += tmp * sign;
    cout << ans;
}

 

 

 

Reference

• https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x11/solutions/1541.cpp