시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1371 183 130 16.435%

문제

여는 괄호와 닫는 괄호로만 이루어져 있으면서, 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 한다.

  1. 빈 문자열은 올바른 괄호 문자열이다.
  2. A가 올바른 괄호 문자열이라면, (A), [A], {A}도 올바른 괄호 문자열이다.
  3. A와 B가 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열이다.

예를 들어, [({})], [](){}, [{}]()[{}]는 올바른 괄호 문자열이다. 하지만, [({{)[, []({)}, [{}])([{}]는 올바른 괄호 문자열이 아니다.

상근이는 책상 서럽에서 올바른 괄호 문자열을 적은 종이를 찾았다. 이 종이는 오래되었기 때문에, 일부 문자는 알아 볼 수 없었다.

알아볼 수 없는 문자를 적절히 괄호로 바꿔서 만들 수 있는 올바른 괄호 문자열의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열의 길이 N이 주어진다. (2 ≤ N ≤ 200)

둘째 줄에는 문자열이 주어진다. 알아볼 수 없는 문자는 '?'로 표시되어 있다.

출력

첫째 줄에 만들 수 있는 올바른 괄호 문자열의 수를 출력한다. 개수가 다섯 자리를 넘어가는 경우에는 마지막 다섯 자리만 출력한다.

예제 입력 1

10
(?([?)]?}?

예제 출력 1

3

힌트

({([()])}), ()([()]{}), ([([])]{})

W3sicHJvYmxlbV9pZCI6IjMwMTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWVjXHViMjk0IFx1YWQwNFx1ZDYzOFx1YzY0MCBcdWIyZWJcdWIyOTQgXHVhZDA0XHVkNjM4XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzRcdWMxMWMsIFx1YjJlNFx1Yzc0YyBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViZTQ4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+QVx1YWMwMCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YmE3NCwgKEEpLCBbQV0sIHtBfVx1YjNjNCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+QVx1YzY0MCBCXHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzdjXHViYTc0LCBBQlx1YjNjNCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBbKHt9KV0sIFtdKCl7fSwgW3t9XSgpW3t9XVx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBbKHt7KVssIFtdKHspfSwgW3t9XSkoW3t9XVx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNjNDVcdWMwYzEgXHVjMTFjXHViN2ZkXHVjNWQwXHVjMTFjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YzgwMVx1Yzc0MCBcdWM4ODVcdWM3NzRcdWI5N2MgXHVjYzNlXHVjNTU4XHViMmU0LiBcdWM3NzQgXHVjODg1XHVjNzc0XHViMjk0IFx1YzYyNFx1Yjc5OFx1YjQxOFx1YzVjOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzc3Y1x1YmQ4MCBcdWJiMzhcdWM3OTBcdWIyOTQgXHVjNTRjXHVjNTQ0IFx1YmNmYyBcdWMyMTggXHVjNWM2XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NGNcdWM1NDRcdWJjZmMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YWQwNFx1ZDYzOFx1Yjg1YyBcdWJjMTRcdWFmZDRcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAyMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNTRjXHVjNTQ0XHViY2ZjIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHViYjM4XHVjNzkwXHViMjk0ICYjMzk7PyYjMzk7XHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMWNcdWMyMThcdWFjMDAgXHViMmU0XHVjMTJmIFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDBcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWIyZTRcdWMxMmYgXHVjNzkwXHViOWFjXHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+KHsoWygpXSl9KSwgKCkoWygpXXt9KSwgKFsoW10pXXt9KTxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzAxMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlpBUElTIiwiZGVzY3JpcHRpb24iOiI8cD5BIHJlZ3VsYXIgYnJhY2tldC1zZXF1ZW5jZSBpcyBhIHN0cmluZyBvZiBjaGFyYWN0ZXJzIGNvbnNpc3Rpbmcgb25seSBvZiBvcGVuaW5nIGFuZCBjbG9zaW5nIGJyYWNrZXRzLCBhbmQgc2F0aXNmeWluZyB0aGUgZm9sbG93aW5nIGNvbmRpdGlvbnM6Jm5ic3A7PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QW4gZW1wdHkgc3RyaW5nIGlzIGEgcmVndWxhciBicmFja2V0LXNlcXVlbmNlLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5JZiBBIGlzIGEgcmVndWxhciBicmFja2V0LXNlcXVlbmNlLCB0aGVuIChBKSwgW0FdIGFuZCB7QX0gYXJlIGFsc28gcmVndWxhciBicmFja2V0LXNlcXVlbmNlcy4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SWYgQSBhbmQgQiBhcmUgcmVndWxhciBicmFja2V0LXNlcXVlbmNlcywgdGhlbiBBQiBpcyBhbHNvIGEgcmVndWxhciBicmFja2V0LXNlcXVlbmNlLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCB0aGUgc2VxdWVuY2VzIFsoe30pXSwgW10oKXt9IGkgW3t9XSgpW3t9XSBhcmUgcmVndWxhciwgYnV0IHRoZSBzZXF1ZW5jZXMgWyh7eyhbLCBbXSh7KX0gYW5kIFt7fV0pKFt7fV0gYXJlIG5vdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SXZpY2EgaGFzIGZvdW5kIGEgc3RyaW5nIHdoaWNoIGxvb2tzIGxpa2UgaXQgY291bGQgYmUgYSByZWd1bGFyIGJyYWNrZXQtc2VxdWVuY2UuIFNvbWUgb2YgdGhlIGNoYXJhY3RlcnMgaGF2ZSBiZWNvbWUgc211ZGdlZCBhbmQgaWxsZWdpYmxlLCBhbmQgY291bGQgaGF2ZSBiZWVuIGFueSBjaGFyYWN0ZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgaG93IG1hbnkgd2F5cyB0aGUgaWxsZWdpYmxlIGNoYXJhY3RlcnMgaW4gdGhlIHN0cmluZyBjYW4gYmUgcmVwbGFjZWQgYnkgYnJhY2tldHMgc28gdGhhdCB0aGUgcmVzdWx0IGlzIGEgcmVndWxhciBicmFja2V0LXNlcXVlbmNlLiBUaGlzIG51bWJlciBjYW4gYmUgdmVyeSBsYXJnZSwgc28gb3V0cHV0IG9ubHkgaXRzIGxhc3QgNSBkaWdpdHMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBldmVuIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAyMDApLCB0aGUgbGVuZ3RoIG9mIHRoZSBzdHJpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyB0aGUgc3RyaW5nLiBJbGxlZ2libGUgY2hhcmFjdGVycyBhcmUgcmVwcmVzZW50ZWQgYnkgdGhlICYjMzk7PyYjMzk7IGNoYXJhY3Rlci48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG51bWJlciBvZiByZWd1bGFyIGJyYWNrZXQtc2VxdWVuY2VzIHRoZSBzdHJpbmcgY291bGQgaGF2ZSByZWFkLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIHRocmVlIG1hdGNoaW5nIHJlZ3VsYXIgYnJhY2tldC1zZXF1ZW5jZXMgYXJlICh7KFsoKV0pfSksICgpKFsoKV17fSkgYW5kIChbKFtdKV17fSkuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #1 4번