[백준/C++] 6604번: Matrix Chain Multiplication(S4)

문제

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

6604번: Matrix Chain Multiplication

 

 

사용한 알고리즘

2022.01.27 - [PS/Algorithm] - [알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱)

-> 스택

 

 

풀이

1. mat[n][2]에 각 행렬의 행과 열의 개수를 담아준다.
   mat[0][0] : A의 행 개수, mat[0][1] : A의 열 개수
   mat[1][0] : B의 행 개수, mat[1][1] : B의 열 개수
   . . .
2. 문자열을 한 줄씩 입력받은 후, 한 글자씩 순회하며 아래 과정을 통해 답을 구해준다.

규칙1. 현재 보고있는 문자 k가 '(' 인 경우,
         스택에 -1을 push해준다.
규칙2. k가 ')'인 경우,
         스택의 마지막 두개 행렬의 곱셈 연산횟수를 ans에 더해주고
         곱셈 결과 생성된 행렬을 error확인 후 push해준다.
규칙3. 스택이 비지 않았고 top()이 -1이 아닌 경우,
         error여부 확인 후 해당 행렬(알파벳)의 행의 개수, 열의 개수를 push해준다. 
규칙4. 스택이 비었거나 top()이 -1인 경우,
         해당 행렬(알파벳)의 행의 개수, 열의 개수를 push해준다. 

 

**
입력받은 문자열(s)이 ( C ( D E ) ) 인 경우를 예로 들어 답을 구해보자.
C행=10, C열=30, D행=30, D열=20, E행=20, E열=40

먼저 stack <int> st를 만들어 준다.

 

규칙1.과 규칙4.에 의해 ( C ( D까지 스택에 push해준다.

-1

C행

C열

-1

D행

D열

 

규칙3.에 의해  E를 push 해준다. -> ( C ( D E
즉, D열!=E열 이라면 error처리하고 break한다.
지금은 D열==E열 이므로 E행 E열을 push 해준다.

-1

C행

C열

-1

D행

D열

E행

E열

                                  

그다음은 )이므로 ( C ( D E )가 되었다.
규칙2.에 의해 DxE를 처리해준다. -> (  C  DxE  
r=E열, m=E행, l=D행을 저장해주며 '('가 나올 때까지 총 5회 pop()해준다.
ans+=l*m*r 해주고 규칙3.에 의해 C열==D행인지 확인 후 l(D행), r(E열)을 push해준다. 

-1

C행

C열

D행

E열

 

이번에도 )이므로 ( C  DxE  )가 되었다.
규칙2.에 의해 CxDxE를 처리해준다. ->  CxDxE 
r=E열, m=D행, l=C행을 저장해주며 '('가 나올 때까지 총 5회 pop()해준다.
ans+=l*m*r 해주고 규칙4.에 의해 l(C행), r(E열)을 push해준다. 

C행

E열

이 과정에서 error가 없었다면 ans를 출력해주면 된다.

끝!

 

 

소스코드

#include <iostream>
#include <stack>

typedef long long ll;
using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int n; cin>>n;
    // mat[n][2]에 각 행렬의 행과 열의 개수를 담아준다.
    int mat[n][2];

    for(int i=0; i<n; i++){
        char c; int x,y;
        cin>>c>>x>>y;
        mat[i][0]=x, mat[i][1]=y;
    }

    string s;
    while(cin>>s){

        stack <int> st;
        int ans=0, ck=1; // error발생 시 ck=0

        for(auto &k:s){
            /* 규칙1.
               현재 보고있는 문자 k가 '(' 인 경우, 스택에 -1을 push해준다. */
            if(k=='(') st.push(-1);
            /* 규칙2.
               k가 ')'인 경우,
               스택의 마지막 두개 행렬의 곱셈 연산횟수를 ans에 더해주고
               곱셈 결과 생성된 행렬을 error확인 후 push해준다. */
            else if(k==')'){
                // (D행 D열 E행 E열)인 경우라면
                int r=st.top(); st.pop(); //E열
                int m=st.top(); st.pop(); st.pop(); //D열, E행
                int l=st.top(); st.pop(); //D행
                st.pop(); // '(' =-1
                ans+=l*m*r; //D행 * E행(=D열) * E열
                if(!st.empty() && st.top()!=-1 && st.top()!=l){ // 앞에있던거랑 행열 안맞으면
                    cout<<"error\n";
                    ck=0;
                    break;
                }
                st.push(l); //D행
                st.push(r); //E열
            }
            else{
            /* 규칙3.
               스택이 비지 않았고 top()이 -1이 아닌 경우,
               error여부 확인 후 해당 행렬(알파벳)의 행의 개수, 열의 개수를 push해준다. */
                if(!st.empty() && st.top()!=-1){ // top()이 알파벳(어떤 행렬)인 경우
                    // D있는 상태에서 E를 넣으려 한다면...
                    // D행 D열 <- E행 E열
                    if(st.top()!=mat[k-'A'][0]){ // D열 != E행
                        cout<<"error\n";
                        ck=0;
                        break;
                    }
                    else{
                        st.push(mat[k-'A'][0]); //E행
                        st.push(mat[k-'A'][1]); //E열
                    }
                }
            /* 규칙4.
               스택이 비었거나 top()이 -1인 경우,
               해당 행렬(알파벳)의 행의 개수, 열의 개수를 push해준다. */
                else{
                    st.push(mat[k-'A'][0]);
                    st.push(mat[k-'A'][1]);
                }
            }
        }
        if(ck) cout<<ans<<'\n';
    }
    return 0;
}

 

이렇게 풀고 나서 생각난 건데

스택에 행, 열 개수를 각각 넣는 게 아니라
pair로 넣거나,
그냥 char들을 넣었다면 코드가 더 간단해졌을 것 같다.