BRACKETS

알고 스팟 BRACKETS

<재귀>
[-] Collapse

#include<iostream>

#include<string>

#include<cstring>

#include<algorithm>

using namespace std;

int cache[101][101];

string s;

int search(int l, int r){

 if (l >= r) return cache[l][r] = 0;

 int& ret = cache[l][r];

 if (ret != -1) return ret;

 ret = 0;

 if (s[l] == '(' && s[r] == ')')

  ret = search(l + 1, r - 1) + 2;

 if (s[l] == '[' && s[r] == ']')

  ret = search(l + 1, r - 1) + 2;

 for (int next = l; next < r; next++)

  ret = max(ret, search(l, next) + search(next+1, r));

 return ret;

}

int main(){

 while (cin >> s){

  if (s == "end") break;

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

  cout << search(0, s.size() - 1) << endl;

 }

}



-------------------------------------------------------------------------

<for문>

[-] Collapse

#include<iostream>

#include<algorithm>

#include<string>

#include<cstring>

using namespace std;

int d[103][103];

int main(){

 string s;

 while (cin >> s){

  if (s == "end") break;

  int n = s.size();

  memset(d, 0, sizeof(d));

  for (int b = 1; b < n; b++) {

   for (int i = 0; i + b < n; i++) {

    int j = i + b;

    d[i][j] = 0;

    if (s[i] == '(' && s[j] == ')')

     d[i][j] = max(d[i][j], d[i + 1][j - 1] + 2);

    if (s[i] == '[' && s[j] == ']')

     d[i][j] = max(d[i][j], d[i + 1][j - 1] + 2);

    for (int k = i; k < j; k++)

     d[i][j] = max(d[i][j], d[i][k] + d[k + 1][j]);

   }

  }

  printf("%d\n", d[0][n - 1]);

 }

 return 0;

}