올바른 괄호 문자열 (BOJ 3012)

문제

이미지 클릭

문제 설명

• (), {}, []는 올바른 괄호 문자열이고 (올바른 괄호 문자열), {올바른 괄호 문자열}, [올바른 괄호 문자열] 또한 올바른 괄호문자열이다. 
• ? 의 경우에는 보이지 않는 괄호기호로 ?에 괄호를 채워서 올바른 문자열을 몇 개 만들 수 있는지 출력해야 한다.

최종 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 100000;
int n;
string s;
ll dp[204][204];
char c1[] = {'(', '{', '['}, c2[] = {')', '}', ']'};
int main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin >> n >> s;
  memset(dp, 0, sizeof(dp));
  if(n%2){
    cout<<0;
    return 0;
  }
  for (int l = 2; l <= n; l += 2) {
    for (int x = 0; x < n - l + 1; x++) {
      int y = x + l - 1;
      for (int i = x + 1; i <= y; i += 2) {
        for (int j = 0; j < 3; j++) {
          if ((s[x] == c1[j] || s[x] == '?') && (s[i] == c2[j] || s[i] == '?')) {
            ll t = 1;
            if (x + 1 <= i - 1) t *= dp[x + 1][i - 1];
            if (i + 1 <= y) t *= dp[i + 1][y];
            dp[x][y] += t;
            if(dp[x][y]>mod) dp[x][y]%=mod, dp[x][y]+=mod;
          }
        }
      }
    }
  }
  string s1=to_string(dp[0][n-1]);
  if(s1.size()<=5) cout<<s1;
  else cout << s1.substr(s1.length()-5, s1.length() - 1);
}

문제 해설

• 길이를 2씩 늘려가면서 범위를 차례로 조절해 준다.

for (int l = 2; l <= n; l += 2)

• x와 l 만큼을 범위로 하여서 탐색을 해준다.

 for (int x = 0; x < n - l + 1; x++) {
      int y = x + l - 1; 
}

• x+1~y 범위에서 +2씩 더하면서 각각의 괄호를 확인해 주는 과정을 진행해 준다. 

for (int i = x + 1; i <= y; i += 2) {for (int j = 0; j < 3; j++) {}}

• 만약 앞의 괄호가 '[', '{', '(' 이거나 '?'이고, 뒤의 괄호가 ']', '}', ')' 이거나 '?'이라면 다음과 같은 수행을 해준다.

1. x+1 <=i-1라면 범위 내부에 존재하기에 dp [x+1][i-1] , 즉 올바른 괄호들의 경우를 t에 곱해준다.
2. i+1 <=y라면 이 또한 범위 내부에 존재하기 때문에 dp [i+1][y], 즉 올바른 괄호들의 경우를 t에 곱해준다.
3. 만약 dp [x][y]가 mod(100000) 보다 크다면 mod로 나눈 나머지를 구한 뒤 mod를 더해준다. 이때 mod를 더해주는 이유는 십만 자릿수 미만을 출력해주어야 하기 때문에 mod를 더하여서 mod를 초과했음을 의미해 준다.

 if ((s[x] == c1[j] || s[x] == '?') && (s[i] == c2[j] || s[i] == '?')) {
            ll t = 1;
            if (x + 1 <= i - 1) t *= dp[x + 1][i - 1];
            if (i + 1 <= y) t *= dp[i + 1][y];
            dp[x][y] += t;
            if(dp[x][y]>mod) dp[x][y]%=mod, dp[x][y]+=mod;
}

• s1의 부분 문자열을 출력해 준다. 만약 부분 문자열을 출력해주지 않는다면 00111 같은 경우에는 111만 출력이 되면서 '틀렸습니다'를 받을 수도 있다.

string s1=to_string(dp[0][n-1]);
  if(s1.size()<=5) cout<<s1;
  else cout << s1.substr(s1.length()-5, s1.length() - 1);

이미지 클릭