SPOJ ANARC09A problem solution(Seinfeld)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

HII GUYS......... This is very good problem for beginners............ this problem can be solved using DP as well as using GREEDY......... I did it using Greedy algorithm........ there is simple logic just traverse the string once u will got the solution MY AC C++ solution is:::: #include<bits/stdc++.h> using namespace std; int main() { int count=0; while(1) { char str[2050]; scanf("%s",str); if(str[0]=='-') break; count++; int i=0,left=0,right=0,ans=0; while(str[i]) { if(str[i]=='{') left++; else { if(str[i]=='}' && left==0) { left++; ans+=1; } else left--; } i++; } ans+=left/2; printf("%d. %d\n",count,ans); } return 0; }