[ 백준 1907 ] 탄소 화합물 (C++)

백준의 탄소 화합물(1907) 문제이다.

[ 문제 바로가기 ]

[ 문제 풀이 ]

1) 가장 먼저 본인은 입력으로 주어진 식을 '3부분'으로 나누어 보았다.

   예제입력 1을 예시로 들어보자면, C+CC=CCCCC에서

   0번 Part = "C", 1번 Part = "CC", 2번 Part = "CCCCC" 이런식으로, '+', '='을 기준으로 파트를 나누어 보았다.

   이 후, 각 파트별로 'C,'H','O'가 몇 개씩 있는지 파악하였다.

   먼저 파트별로 갯수를 어떻게 카운트 해줬는지부터 알아보자.

   화학식은 <분자>[숫자] 꼴의 형태로 이루어져있다고 문제에서 제시했다.

   즉, 예를 들어서 HO2가 있다면, 이는 H는 1개, O는 2개가 있음을 의미한다.

   지금부터 각 파트별로, 하나하나 문자들을 비교하면서 진행해 볼 것이다.

   여기서 우리가 신경써야 할 것은 "갯수를 의미하는 숫자는, 분자 뒤에 나온다" 라는 것을 계속 생각해 주어야 한다.

   즉, 분자(C, H, O) 중 하나를 만났을 경우, 그 뒤에 숫자까지 계산을 해서 갯수를 갱신해 주어야 한다.

   그럼 가장 간단하게, 예제입력 1의 0번 파트(C) 와 예제입력 2의 0번파트(HO3H2) 2개를 예시로 삼고 알아보자.

   먼저, 예제입력 2의 0번파트(HO3H2)를 생각해보자.

   가장 먼저 문자 'H'를 만나게 된다. 분자 중 하나를 만났을 경우에는 그 뒤에 숫자까지 생각해 주어야 한다 !!!

   그렇다면 'H'그 다음 문자를 확인해보자. 'O'가 나오게된다. 이런.... 숫자가 아니라 또 다른 분자가 나오는 경우가

   이렇게 존재한다. 왜 ? H가 1개만 있을때는 '1'이 생략되어서 이렇게 표현이 되기 때문이다.

   따라서, 이 경우를 'Case1' 로 표시하겠다.(소스코드 참고)

   Case1에서는 "현재 문자의 갯수를 +1"을 해주면 된다.

   정리하자면, 분자의 갯수를 확인하기 위해서 분자 다음 값을 확인했는데 숫자가 아닌 분자가 나왔을 경우는 그 분자는 1개만

   있다는 것을 의미하기 때문에 +1을 해준 것이다.

   그렇다면 그 다음 문자 'O'로 넘어가보자. 숫자를 확인하기 위해서 그 다음 문자를 확인해보니 '3'이 나왔다.

   이 경우를 'Case2'로 표시하겠다.

   Case2에서는 "현재 문자의 갯수를 +그 다음 문자" 만큼 해주면 된다. 왜 ? 그 갯수만큼 존재한다는 이야기 이기 때문이다.

   이어서 그 다음 문자를 확인해보자. '3'이 나오게 된다. 그런데 이 '3'은 무슨 의미일까? 이미 이전에 탐색을 했던

   'O'에 의해서 이미 계산된 숫자일 뿐이기 때문에 그냥 넘어가도 상관이 없다. 이 경우를 'Case3'으로 표시해보겠다.

   쭉 탐색을 하다보면 마지막 '2'까지 오게될 것이고, 이 '2' 또한 이미 계산된 숫자라서 넘어 가게 될 것이다.

   그런데 ! 예제입력 1을 한번 봐보도록 하자. 0번 파트가 'C'하나뿐이다.

   'C'를 만나서, 그 다음 문자를 봤더니, 그 다음 문자는 0번 파트에 존재하지 않았다. 즉, 예제입력2처럼 숫자로 한 파트가

   끝이 나는 경우가 있는 반면, 예제입력1처럼 분자로 한 파트가 끝이 나는 경우가 존재한다.

   이 경우를 'Case4'로 표시하겠다. 이 경우에는, '1'이 생략된 것이므로 분자의 수 + 1을 해주면 된다.

2) 이렇게 미리 계산을 모두 끝내놓고 그 다음 본인이 한 것은 "중복순열 구현"이다.

   우리는 주어진 이 식에서 1 ~ 10까지의 숫자들을 3파트에 적절히 넣어보면서 그 갯수를 맞추는 작업을 해야 한다.

   즉, 3파트에 { 1, 1, 1, } 부터, { 10, 10, 10 } 까지 모두 넣어보는 것이다.

   이렇게 해봤자 10 x 10 x 10 = 1000으로 제한시간인 2초내에 충분히 가능한 경우의 수이다.

   아직 중복순열을 모른다면 아래의 글을 읽어보도록 하자.

   [ 중복순열 알아보러가기(Click) ]

  

   이렇게 중복순열을 뽑았다고 생각해보자. 그럼 이제 어떻게 하면 될까 ??

   처음으로 돌아가서 식을 다시 생각해보자. 주어진 식은 0번파트 + 1번파트 = 2번파트 꼴로 존재한다.

   즉, { 1, 1, 1 }을 뽑았다고 생각해보면, 0번파트에 있는 모든 분자들의 수 x1 + 2번파트에 있는 모든 분자들의 수 x1 =

   2번 파트에 있는 모든 분자들의 수 x1 이 일치하는지만 확인해주면 된다.

   이걸 어떻게 확인할까?? 이거를 위해서 우리는 미리 계산을 해 놓은 것이다 !

   예를 들어서 뽑은 중복순열의 값이 { a, b, c } 라고 가정해보자.

   그렇다면 지금부터 계산 해야될 것은 다음과 같다.

   a * (0번 파트의 'C'의 갯수) + b * (1번 파트의 'C'의 갯수) = c * (2번 파트의 'C'의 갯수)

   a * (0번 파트의 'H'의 갯수) + b * (1번 파트의 'H'의 갯수) = c * (2번 파트의 'H'의 갯수)

   a * (0번 파트의 'O'의 갯수) + b * (1번 파타의 'O'의 갯수) = c * (2번 파트의 'O'의 갯수)

   이것들을 계산해주면 된다 ! 본인을 이를 위해서 0번파트 + 1번파트 부분을 'Left[]'로 통일해주었고,

   2번파트를 Right[]로 만들어 주었다.

   일치하는지 판단하기 위해서는 'Right에서 Left를 뺀 값이 0' 이면 갯수가 동일하게 일치한다고 판단할 수 있다

[ 소스코드 ]

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define C 0
#define H 1
#define O 2
using namespace std;
 
string Inp;        // 주어진 입력
string Part[3];    // 3개의 파트로 나누어서 계산.
 
vector<int> Select;
int Atom_Cnt[3][3], Left[3], Right[3];
/* Atom_Cnt[a][b]의 의미
   Atom_Cnt[a][b] = c 의 의미는
   "a번 파트에, 분자 'b'는 c개 존재합니다." 를 의미한다. */
 
void Input()
{
    cin >> Inp;
    int Plus_Idx, Equal_Idx;
    for (int i = 0; i < Inp.length(); i++)
    {
        if (Inp[i] == '+') Plus_Idx = i;
        if (Inp[i] == '=') Equal_Idx = i;
    }
 
    /* 지금부터 주어진 입력을 3개의 파트로 나누는 작업. ('+'와 '='을 기준으로) */
    for (int i = 0; i < Plus_Idx; i++) Part[0] = Part[0] + Inp[i];
    for (int i = Plus_Idx + 1; i < Equal_Idx; i++) Part[1] = Part[1] + Inp[i];
    for (int i = Equal_Idx + 1; i < Inp.length(); i++) Part[2] = Part[2] + Inp[i];
}
 
bool Check()
{
    /* 중복순열을 구현했다면, 계수가 일치하는지 확인하기 위한 함수. */
    int N1 = Select[0];
    int N2 = Select[1];
    int N3 = Select[2];
    
    /* Left[3], Right[3]의 의미 
       Left는 '='을 기준으로 왼쪽에 있는 식(파트 0 + 파트 1)
       Right는 '='을 기준으로 오른쪽에 있는 식(파트 2)
       중복순열 구현을 통해서 얻어온 계수들을, 각 파트에 분자들의 기존의 수에 곱해주고
       더해주는 작업을 통해서 '='을 기준으로 갯수가 일치하는지 확인한다.  */
    Left[C] = N1 * Atom_Cnt[0][C] + N2 * Atom_Cnt[1][C];
    Left[H] = N1 * Atom_Cnt[0][H] + N2 * Atom_Cnt[1][H];
    Left[O] = N1 * Atom_Cnt[0][O] + N2 * Atom_Cnt[1][O];
 
    Right[C] = N3 * Atom_Cnt[2][C];
    Right[H] = N3 * Atom_Cnt[2][H];
    Right[O] = N3 * Atom_Cnt[2][O];
 
    /* 갯수가 일치한다면, 뺏을 때 0이 나와야 한다. 일치하지 않는다면 당연히 0이 안나오게 된다.*/
    for (int i = 0; i < 3; i++)
    {
        if (Left[i] - Right[i] != 0) return false;
    }
    return true;
}
 
void DFS(int Cnt)
{
    /* 계수를 뽑아내기 위해서 중복순열을 구현하기 위한 DFS 함수. */
    if (Cnt == 3)
    {
        memset(Left, 0, sizeof(Left));
        memset(Right, 0, sizeof(Right));
        if (Check() == true)
        {
            for (int i = 0; i < 3; i++) cout << Select[i] << " ";
            exit(0);
        }
        return;
    }
 
    for (int i = 1; i < 11; i++)
    {
        Select.push_back(i);
        DFS(Cnt + 1);
        Select.pop_back();
    }
}
 
void Counting()
{
    /* 미리 갯수를 Count해주는 작업을 하기 위한 함수. */
 
    for (int i = 0; i < 3; i++)    // 각 파트별로 진행하겠다.
    {
        for (int Cur = 0; Cur < Part[i].size(); Cur++)
        {
            if ('2' <= Part[i][Cur] && Part[i][Cur] <= '9') continue;
            /* 위의 조건문이 'Case3'에 해당하는 조건문.
               숫자는, 이미 분자가 나왔을 때 계산을 했기 때문에 그냥 지나쳐도 무방. */
 
            int Next = Cur + 1;            
            /* 항상 그 다음 문자까지 확인해주어야한다. 
               [분자]<숫자> 꼴이므로(Cur = 현재문자 , Next = 다음문자) */ 
            
            if (Next >= Part[i].size())    
            {
                /* 'Case4' 에 해당하는 조건문.
                    한 파트의 마지막이 숫자로 끝났다면, 위의 'Case3'을 가르키는 조건문에 의해서
                    여기까지 오지도 않았을 것이다. 
                    지금 이 조건문에 걸렸다는 말은, 예제입력1과 같이, 한 파트의 마지막이 분자로 끝나는 경우 */
                if (Part[i][Cur] == 'C') Atom_Cnt[i][C] = Atom_Cnt[i][C] + 1;
                else if (Part[i][Cur] == 'H') Atom_Cnt[i][H] = Atom_Cnt[i][H] + 1;
                else if (Part[i][Cur] == 'O') Atom_Cnt[i][O] = Atom_Cnt[i][O] + 1;
                continue;
            }
 
            if (!('2' <= Part[i][Next] && Part[i][Next] <= '9'))
            {
                /* 'Case1' 에 해당하는 조건문 
                   <분자>[숫자] 꼴이지만, 해당 분자가 1개만 있을 경우에는 '1'이 생략되어서
                   다음 문자로 또 다른 분자가 나오게 된다.
                   즉, 현재 문자는 분자인데, 다음 문자가 숫자가 아닐 경우 '1'개를 의미. */
                if (Part[i][Cur] == 'C') Atom_Cnt[i][C] = Atom_Cnt[i][C] + 1;
                else if (Part[i][Cur] == 'H') Atom_Cnt[i][H] = Atom_Cnt[i][H] + 1;
                else if (Part[i][Cur] == 'O') Atom_Cnt[i][O] = Atom_Cnt[i][O] + 1;
                continue;
            }
            else
            {
                /* 'Case2' 에 해당하는 조건문.
                   <분자>[숫자] 꼴에 알맞게, 현재 문자로 분자가 나와서 그 다음 문자를 확인했더니
                   숫자가 존재한다. 그럼, 그 분자는 그 숫자만큼 존재한다는 것을 의미하게 된다. */
                int Num = Part[i][Next] - '0';
                if (Part[i][Cur] == 'C') Atom_Cnt[i][C] = Atom_Cnt[i][C] + Num;
                else if (Part[i][Cur] == 'H') Atom_Cnt[i][H] = Atom_Cnt[i][H] + Num;
                else if (Part[i][Cur] == 'O') Atom_Cnt[i][O] = Atom_Cnt[i][O] + Num;
            }
        }
    }
}
 
void Solution()
{
    Counting();
    DFS(0);
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}