[2257번] 화학식량

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 재귀

재귀를 이용하여 문제를 풀 수 있다.

사실 이 문제는 stack을 이용하여 문제를 풀 수 있지만, 라이브러리를 사용 할 수 없는 환경이라면 다음과같이 내부 stack을 이용하여서도 풀 수 있다.

tmp는 이전 문자가 뭔지 의미해주고 있고, ret는 실제로 결과값에 영향을 끼치는 값이다.

'('를 만난다면 재귀 호출을 통해 ')'가 나오기 전까지 모든값을 담아내주고,

')'를 만날 때는 ')'이후에 숫자가 존재하는지 파악해준 후 있다면 곱해서 retrun을 그렇지 않다면 ret를 return해준다.

그 외 숫자는 그냥 ret에 계산을 해준다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <string>
 
#define H 1
#define C 12
#define O 16
 
using namespace std;
 
bool visit[102];
 
int tmp;
int dfs(string str, int pos, int len)
{
    int ret = 0;
    for (int i = pos; i < len; i++)
    {
        if (visit[i])
            continue;
        visit[i] = true;
 
        if (str[i] == 'H') ret += H, tmp = H;
        else if (str[i] == 'O') ret += O, tmp = O;
        else if (str[i] == 'C') ret += C, tmp = C;
 
        else if (str[i] == '(')
        {
            ret += dfs(str, i + 1, len);
        }
        else if (str[i] == ')')
        {
            if ('2' <= str[i + 1] && str[i + 1] <= '9')
            {
                visit[i + 1] = true;
                ret *= (str[i + 1] - '0');
            }
            return ret;
        }
        else if ('2' <= str[i] && str[i] <= '9')
        {
            ret += (tmp * (str[i] - '0')) - tmp;
        }
    }
    return ret;
}
int main()
{
    string str;
    cin >> str;
 
    int len = str.size();
 
    cout << dfs(str, 0, len);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>