백준 3012번 올바른 괄호 문자열

문제 링크입니다: https://www.acmicpc.net/problem/3012

로직 자체는 쉬운 편이였지만 끝에 다섯자리만 출력하기 위해서 모듈러 연산을 적절히 해줘야하는데 그 부분은 백준님 코드를 참고했습니다.

알고리즘은 아래와 같습니다.

1. 범위 [시작, 끝]을 정해놓고 여기서 분할 탐색을 하며 적절한 쌍을 이루는지 파악합니다.

2. 예를 들어 start번째 인덱스의 쌍이 i번째 인덱스라면 (start + 1) ~ (i - 1) 구간과 (i + 1) ~ end 구간을 분할 탐색해주며 쌍을 이루는지 파악합니다.

3. 괄호가 명시되어있는 경우 무조건 해당 괄호랑만 쌍이지만 괄호가 명시되어있지 않고 ?라면 조커처럼 모든 경우에 대응해줄 수 있으므로 적절히 조건문을 작성해줘야합니다.

#include <iostream>

#include <string>

#include <cstring>

using namespace std;

 

const long long MOD = 100000;

const int MAX = 200;

 

int N;

string s;

long long cache[MAX][MAX];

string open = "({[", close = ")}]";

 

 

long long func(int start, int end)

{

        //조건 만족

        if (start > end)

                 return 1;

 

        long long &result = cache[start][end];

        if (result != -1)

                 return result;

 

        result = 0;

        //+=2인 이유는 그 사이도 쌍이 생겨야하므로

        for (int i = start + 1; i <= end; i += 2)

                 for(int j=0; j<open.size(); j++)

                         if(s[start] == open[j] || s[start] == '?')

                                 if (s[i] == close[j] || s[i] == '?')

                                 {

                                          //start와 짝이 맞는 괄호의 위치 i

                                          //따라서 (start+1) ~ (i-1) 과 (i+1) ~ end 구간을 분할 탐색

                                          long long temp = func(start + 1, i - 1) * func(i + 1, end);

                                          result += temp;

                                          if (result >= MOD)

                                                  result = MOD + result % MOD;

                                 }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> s;

 

        memset(cache, -1, sizeof(cache));

        long long result = func(0, N - 1);

 

        if (result >= MOD)

                 printf("%05lld\n", result%MOD);

        else

                 cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~