시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB379270247821.473%

문제

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

10
(?([?)]?}?

예제 출력 1

3

예제 입력 2

6
()()()

예제 출력 2

1

예제 입력 3

16
???[???????]????

예제 출력 3

92202

힌트

예제 1의 경우 다음이 가능하다. ({([()])}), ()([()]{}), ([([])]{})

W3sicHJvYmxlbV9pZCI6IjMwMTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNWVjXHViMjk0IFx1YWQwNFx1ZDYzOFx1YzY0MCBcdWIyZWJcdWIyOTQgXHVhZDA0XHVkNjM4XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzRcdWMxMWMsIFx1YjJlNFx1Yzc0YyBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViZTQ4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+QVx1YWMwMCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1Yjc3Y1x1YmE3NCwgKEEpLCBbQV0sIHtBfVx1YjNjNCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuXHQ8bGk+QVx1YzY0MCBCXHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViNzdjXHViYTc0LCBBQlx1YjNjNCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBbKHt9KV0sIFtdKCl7fSwgW3t9XSgpW3t9XVx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBbKHt7KVssIFtdKHspfSwgW3t9XSkoW3t9XVx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNjNDVcdWMwYzEgXHVjMTFjXHViNzhkXHVjNWQwXHVjMTFjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQ0IFx1YzgwMVx1Yzc0MCBcdWM4ODVcdWM3NzRcdWI5N2MgXHVjYzNlXHVjNTU4XHViMmU0LiBcdWM3NzQgXHVjODg1XHVjNzc0XHViMjk0IFx1YzYyNFx1Yjc5OFx1YjQxOFx1YzVjOFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzc3Y1x1YmQ4MCBcdWJiMzhcdWM3OTBcdWIyOTQgXHVjNTRjXHVjNTQ0IFx1YmNmYyBcdWMyMTggXHVjNWM2XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NGNcdWM1NDRcdWJjZmMgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWJiMzhcdWM3OTBcdWI5N2MgXHVjODAxXHVjODA4XHVkNzg4IFx1YWQwNFx1ZDYzOFx1Yjg1YyBcdWJjMTRcdWFmZDRcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAyMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNTRjXHVjNTQ0XHViY2ZjIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHViYjM4XHVjNzkwXHViMjk0ICYjMzk7PyYjMzk7XHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMWNcdWMyMThcdWFjMDAgXHViMmU0XHVjMTJmIFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWIxMThcdWM1YjRcdWFjMDBcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWIyZTRcdWMxMmYgXHVjNzkwXHViOWFjXHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHVjODFjIDFcdWM3NTggXHVhY2JkXHVjNmIwIFx1YjJlNFx1Yzc0Y1x1Yzc3NCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuIDxjb2RlPih7KFsoKV0pfSk8XC9jb2RlPiwgPGNvZGU+KCkoWygpXXt9KTxcL2NvZGU+LCA8Y29kZT4oWyhbXSlde30pPFwvY29kZT48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwMTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJaQVBJUyIsImRlc2NyaXB0aW9uIjoiPHA+QSByZWd1bGFyIGJyYWNrZXQtc2VxdWVuY2UgaXMgYSBzdHJpbmcgb2YgY2hhcmFjdGVycyBjb25zaXN0aW5nIG9ubHkgb2Ygb3BlbmluZyBhbmQgY2xvc2luZyBicmFja2V0cywgYW5kIHNhdGlzZnlpbmcgdGhlIGZvbGxvd2luZyBjb25kaXRpb25zOiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkFuIGVtcHR5IHN0cmluZyBpcyBhIHJlZ3VsYXIgYnJhY2tldC1zZXF1ZW5jZS4mbmJzcDs8XC9saT5cclxuXHQ8bGk+SWYgQSBpcyBhIHJlZ3VsYXIgYnJhY2tldC1zZXF1ZW5jZSwgdGhlbiAoQSksIFtBXSBhbmQge0F9IGFyZSBhbHNvIHJlZ3VsYXIgYnJhY2tldC1zZXF1ZW5jZXMuJm5ic3A7PFwvbGk+XHJcblx0PGxpPklmIEEgYW5kIEIgYXJlIHJlZ3VsYXIgYnJhY2tldC1zZXF1ZW5jZXMsIHRoZW4gQUIgaXMgYWxzbyBhIHJlZ3VsYXIgYnJhY2tldC1zZXF1ZW5jZS4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgdGhlIHNlcXVlbmNlcyBbKHt9KV0sIFtdKCl7fSBpIFt7fV0oKVt7fV0gYXJlIHJlZ3VsYXIsIGJ1dCB0aGUgc2VxdWVuY2VzIFsoe3soWywgW10oeyl9IGFuZCBbe31dKShbe31dIGFyZSBub3QuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkl2aWNhIGhhcyBmb3VuZCBhIHN0cmluZyB3aGljaCBsb29rcyBsaWtlIGl0IGNvdWxkIGJlIGEgcmVndWxhciBicmFja2V0LXNlcXVlbmNlLiBTb21lIG9mIHRoZSBjaGFyYWN0ZXJzIGhhdmUgYmVjb21lIHNtdWRnZWQgYW5kIGlsbGVnaWJsZSwgYW5kIGNvdWxkIGhhdmUgYmVlbiBhbnkgY2hhcmFjdGVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIGhvdyBtYW55IHdheXMgdGhlIGlsbGVnaWJsZSBjaGFyYWN0ZXJzIGluIHRoZSBzdHJpbmcgY2FuIGJlIHJlcGxhY2VkIGJ5IGJyYWNrZXRzIHNvIHRoYXQgdGhlIHJlc3VsdCBpcyBhIHJlZ3VsYXIgYnJhY2tldC1zZXF1ZW5jZS4gVGhpcyBudW1iZXIgY2FuIGJlIHZlcnkgbGFyZ2UsIHNvIG91dHB1dCBvbmx5IGl0cyBsYXN0IDUgZGlnaXRzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gZXZlbiBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMjAwKSwgdGhlIGxlbmd0aCBvZiB0aGUgc3RyaW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgdGhlIHN0cmluZy4gSWxsZWdpYmxlIGNoYXJhY3RlcnMgYXJlIHJlcHJlc2VudGVkIGJ5IHRoZSAmIzM5Oz8mIzM5OyBjaGFyYWN0ZXIuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBudW1iZXIgb2YgcmVndWxhciBicmFja2V0LXNlcXVlbmNlcyB0aGUgc3RyaW5nIGNvdWxkIGhhdmUgcmVhZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSB0aHJlZSBtYXRjaGluZyByZWd1bGFyIGJyYWNrZXQtc2VxdWVuY2VzIGFyZSAoeyhbKCldKX0pLCAoKShbKClde30pIGFuZCAoWyhbXSlde30pLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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