SRM 521

오랜만에 참가했다..
요즘 다리를 다쳐서 컨디션도 안좋은데.. 스름도 망쳤다..
덕분에 다시 blue 로 떨어지고.. 젠장.. 괜히 참가했다..

ㅠ_ㅠ


250 문제는 당연히 DP 구나 하고 마구 풀었는데.. 나중에 남들 코드 보고 화들짝 놀랐다.. -_-
아주 간단한 greedy 해결방법이 있었다.. 어쩐지 다들 빨리 풀더라니..
나이를 먹다보니.. 뭔가 참신한 생각이 안나온다..

  1 #include <iostream>

  2 #include <cstdio>

  3 #include <algorithm>

  4 #include <vector>

  5 #include <string>

  6 using namespace std;

  7 #define min(x, y) ((x) > (y) ? (y) : (x))

  8 //#define max(x, y) ((x) > (y) ? (x) : (y))

  9 #define INF 999999999

 10 //#define EPS 1e-14

 11

 12 int memo[100][100];

 13 int len;

 14 string str;

 15

 16 int recur(int l, int r)

 17 {

 18     int res, temp, i;

 19     if (l == r)

 20         return 1;

 21     if (l > r)

 22         return 0;

 23     if (memo[l][r] != -1)

 24         return memo[l][r];

 25     res = INF;

 26     if (str[l] == '(' && str[r] == ')') {

 27         temp = recur(l+1, r-1);

 28         if (temp < res)

 29             res = temp;

 30     }

 31     else {

 32         temp = min(recur(l+1, r) + 1, recur(l, r-1) + 1);

 33         if (temp < res)

 34             res = temp;

 35     }

 36     for (i = l; i < r; i++) {

 37         temp = recur(l, i) + recur(i+1, r);

 38         if (temp < res)

 39             res = temp;

 40     }

 41     return memo[l][r] = res;

 42 }

 43

 44 class MissingParentheses {

 45 public:

 46

 47 int countCorrections(string par)

 48 {

 49     int res;

 50     str = par;

 51     len = str.size();

 52     memset(memo, -1, sizeof(memo));

 53     res = recur(0, len-1);

 54     return res;

 55 }

 56

 57 };