[2257번] 화학식량(재귀함수 풀이)

이 문제는 스택으로 풀 수도 있다고 한다. 이번 해설에서는 재귀함수를 통해서 설명하겠다.

 

문제접근법.

1. 한 문자가 무엇인지에 따라서, 알맞는 연산의 과정이 필요

2. 괄호가 등장했을 때, 특별한 연산이 필요

 

이 두 가지에 초점을 맞춰서 재귀 함수를 구성하면 된다. 1번은 알파벳 두개가 연달아 나왔을 때와, 숫자가 나왔을 때를 생각해주면 조건문을 작성할 수 있다. 2번은 좀 까다롭다. 예시는 다음과 같다.

 

(H(O2)3)2를 보면, 괄호가 두 개 나와 있다.

 

괄호가 두 개 이상있을 때 방법을 생각하는게 문제의 핵심이다. 괄호가 열리기 전까지 연산된 값을 기록해두고 괄호가 닫히면 기록된 값을 이용해서 연산을 진행하면 문제를 해결할 수 있다.

 

 

해설 코드(C++) 

#include <iostream>
#include <cstring>
using namespace std;
string s;
int answer = 0;
int temp[101] = { 0 };
int temp_idx = 0;
 
void recur(int idx, int sum) {
    if (idx == s.length()) {
        answer += sum;
        return;
    }
 
    if (s.at(idx) == 'H') {
        if (sum != 0)
            answer += sum;
        recur(idx + 1, 1);
    }
    else if (s.at(idx) == 'C') {
        if (sum != 0)
            answer += sum;
        recur(idx + 1, 12);
    }
    else if (s.at(idx) == 'O') {
        if (sum != 0)
            answer += sum;
        recur(idx + 1, 16);
    }
    else if (s.at(idx) >= '1' && s.at(idx) <= '9') {
        answer += (sum * (s.at(idx) - '0'));
        recur(idx + 1, 0);
    }
    else if (s.at(idx) == '(') {
        answer += sum;
        temp[temp_idx++] = answer;
        recur(idx + 1, 0);
    }
    else if (s.at(idx) == ')') {
        int t2 = answer + sum;
        answer = temp[--temp_idx];
        recur(idx + 1, t2 - temp[temp_idx]);
    }
}
 
int main(void) {
    freopen("input.txt", "r", stdin);
    cin >> s;
 
    memset(temp, 0, sizeof(temp));
 
    recur(0, 0);
    cout << answer << endl;
    return 0;
}