백준 2504 c++ // 스택응용

https://www.acmicpc.net/problem/2504

2504번: 괄호의 값

*의사코드

 

 

 

*요약

이해가잘안갔던 문제이다.

          ( ( ) 이면

num : 2 4 2  이고

sum에 4를 더해준다.

 

첫닫는과호를 만났을때 바깥괄호의 영향까지 포함해서 계산을 마치고 sum을 갱신하고, 

이후 좌측괄호의 영향이 안가도록 num을 나눠준다

그리디 분류에도 속할것 같다.

 

*전체코드

// Authored by : std-freejia
// Co-authored by : BaaaaaaaaaaarkingDog, rhsnfl1122
// http://boj.kr/cbef82389d1048db80c9652d18b71304
#include <bits/stdc++.h>
using namespace std;

stack<char> s;
string str;

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

    cin >> str;
    int sum = 0; // 누적해서 더해질 값
    int num = 1; // 곱해질 값

    /*
    * 1. 바깥괄호는 모든내부에대해 영향을준다
    * ex)  [((이면, [괄호 우측 괄호들은 모두*3이다.
    * 2. 구현방법 : num을만들고
    * 해당점수를 곱해 우측괄호에 영향을미치도록한다.
    * 3. 첫 좌괄호( 를 만날때만 sum을 갱신한다. 
         <= 좌측 num 에서 해당값만큼 이미 곱해줫음
    * 
    */
        
    for (int i = 0; i < str.size(); i++) {

        //cout << "합 : " << sum << "\n";

        if (str[i] == '(') {
            s.push(str[i]);
            num *= 2;
        }
        else if (str[i] == '[') {
            s.push(str[i]);
            num *= 3;
        }
        else if (str[i] == ')') {
            if (s.empty() || s.top() != '(') {
                cout << 0;
                return 0;
            }
            //첫 )닫는괄호 만날때만 sum갱신
            //해당 괄호 계산을 마친다.
            //ex : (() 이면 4(2*2)를 합한다.
            if (str[i - 1] == '(') {
                sum += num;
            }
            // () 끝났으니까 영향을 없앤다.
            num /= 2;
            s.pop();
                 
        }
        else { // str[i] == ']'
            if (s.empty() || s.top() != '[') {
                cout << 0;
                return 0;
            }
            if (str[i - 1] == '[') {
                sum += num;
            }
            num /= 3;
            s.pop();
            
        }
    }
    if (s.empty()) cout << sum;
    else cout << 0;
}

/*
boj 10799 쇠 막대기 문제의 아이디어와 비슷하게 붙어있는 () 혹은 []를 만나면
sum에 점수를 더해줌. () 혹은 []이 몇 점인가는 중첩된 소괄호/대괄호의 곱으로
계산 가능하고 이는 변수 num에 저장이 됨.
*/