백준 1662 압축 혼내주기

 

1차 삽질 - 스택에 char 단위로 넣고 빼다가 메모리초과.
2차 삽질 - 스택에 string 단위로 넣고 빼다가 메모리초과.
결국 스택에서 재귀로 바꿔서 구현했다.
생각해보면 9(9(9(9(9(9(9(9(9(9))))))))))))) 이런식으로 들어오면 string이어도 길이가 터무니없이 길어지는데, 충분히 생각하지 않고 풀기 시작해서 삽질하게 되었다.

 

문제를 읽고 최악의 경우를 항상 생각하자.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

bool visited[50];
string s;

void input() {
    fastio;
    cin >> s;
}

int d(int idx) {
    int ret = 0;

    for(int i = idx; i < s.size(); ++i) {
        if(!visited[i] && s[i] == '(') {
            visited[i] = true;
            ret += (s[i-1]-'0') * d(i+1) - 1;
        }
        else if(!visited[i] && s[i] == ')') {
            visited[i] = true;
            return ret;
        }
        else if(!visited[i]) {
            visited[i] = true;
            ret++;
        }
    }
    return ret;
}

int main() {
    input();
    cout << d(0);
}