오랜만에 참가했다..
요즘 다리를 다쳐서 컨디션도 안좋은데.. 스름도 망쳤다..
덕분에 다시 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 };




'Problem Solving > TopCoder logs' 카테고리의 다른 글

TCO13 Round 1C 생명연장 매치  (0) 2013.03.10
TCO12 R1A - 606등 -_-;;  (0) 2012.04.01
SRM 529  (0) 2012.01.15
SRM 521  (0) 2011.10.24
SRM 511  (0) 2011.07.04
TCO11 R1 - 탈락  (0) 2011.06.23
SRM 509 !!  (0) 2011.06.09
SRM 507 - 나이스!  (0) 2011.05.30
TCO11 Qual2  (0) 2011.05.20
TCO11 Qual1  (2) 2011.05.15
SRM 504 - unrated event  (0) 2011.04.27

Leave a Comment


to Top