시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 87 34 28 49.123%

문제

올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키파를 도와 올바른 괄호쌍이 되도록 고쳐 주자.

키파는 괄호를 입력할 때 매우 조심했기 때문에 최대 한 번 오타를 내었다. 올바른 괄호쌍은 다음과 같이 정의된다:

  • ()는 올바른 괄호쌍이다.
  • A가 올바른 괄호쌍이라면 (A) 또한 올바른 괄호쌍이다.
  • A와 B가 올바른 괄호쌍이라면 AB 또한 올바른 괄호쌍이다.

입력

첫째 줄에 키파가 입력한 괄호열이 주어진다. 길이는 1 이상 100,000 이하이다.

출력

첫째 줄에 하나의 문자만 고쳐서 올바른 괄호쌍이 될 수 있는 경우의 수를 출력한다.

예제 입력 1

()(())))

예제 출력 1

4

힌트

키파가 입력한 다음 문자열을 자세히 보자:

12345678
()(())))

2번째 문자 )를 (로 고침으로써 올바른 문자열을 만들 수 있다:

12345678
(((())))

비슷하게, 5번째 문자, 6번째 문자, 혹은 7번째 문자를 고침으로써 올바른 문자열을 만들 수 있다.

W3sicHJvYmxlbV9pZCI6IjU4NzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MjRcdWQwYzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzhcdWMzMGRcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1ZDBhNFx1ZDMwY1x1YjI5NCBcdWNkNWNcdWFkZmNcdWM1ZDAgXHViMTc4XHVkMmI4XHViZDgxXHVjNzQ0IFx1YzBjMFx1YjJlNC4mbmJzcDtcdWFkZjhcdWI3ZjBcdWIzNzAmbmJzcDtcdWQwYTRcdWJjZjRcdWI0ZGNcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YjEwOFx1YmIzNCBcdWM3OTFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWQwYTRcdWQzMGNcdWIyOTQgXHVkNjM5XHVjMmRjJm5ic3A7XHVjNWVjXHViMjk0IFx1YWQwNFx1ZDYzOFx1YzY0MCBcdWIyZWJcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1YzExY1x1Yjg1YyBcdWM3OThcdWJhYmIgXHVjNzg1XHViODI1XHVkNTU4XHVjOWMwJm5ic3A7XHVjNTRhXHVjNTU4XHViMjk0XHVjOWMwIFx1YWM3MVx1YzgxNVx1YjQxOFx1YzVjOFx1YjJlNC4mbmJzcDtcdWQwYTRcdWQzMGNcdWI5N2MgXHViM2M0XHVjNjQwIFx1YzYyY1x1YmMxNFx1Yjk3OCZuYnNwO1x1YWQwNFx1ZDYzOFx1YzMwZFx1Yzc3NCBcdWI0MThcdWIzYzRcdWI4NWQmbmJzcDtcdWFjZTBcdWNjZDAgXHVjOGZjXHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWQwYTRcdWQzMGNcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1Yzc4NVx1YjgyNVx1ZDU2MCBcdWI1NGMgXHViOWU0XHVjNmIwIFx1Yzg3MFx1YzJlY1x1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjZDVjXHViMzAwIFx1ZDU1YyBcdWJjODggXHVjNjI0XHVkMGMwXHViOTdjIFx1YjBiNFx1YzVjOFx1YjJlNC4gXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOFx1YzMwZFx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzgxNVx1Yzc1OFx1YjQxY1x1YjJlNDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4oKVx1YjI5NCBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4XHVjMzBkXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5BXHVhYzAwIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzhcdWMzMGRcdWM3NzRcdWI3N2NcdWJhNzQgKEEpIFx1YjYxMFx1ZDU1YyBcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4XHVjMzBkXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5BXHVjNjQwIEJcdWFjMDAgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOFx1YzMwZFx1Yzc3NFx1Yjc3Y1x1YmE3NCBBQiBcdWI2MTBcdWQ1NWMgXHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOFx1YzMwZFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQwYTRcdWQzMGNcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YWQwNFx1ZDYzOFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWUzOFx1Yzc3NFx1YjI5NCAxIFx1Yzc3NFx1YzBjMSAxMDAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJiMzhcdWM3OTBcdWI5Y2MgXHVhY2UwXHVjY2QwXHVjMTFjJm5ic3A7XHVjNjJjXHViYzE0XHViOTc4IFx1YWQwNFx1ZDYzOFx1YzMwZFx1Yzc3NCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjJm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWQwYTRcdWQzMGNcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YjJlNFx1Yzc0YyBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjNzkwXHVjMTM4XHVkNzg4IFx1YmNmNFx1Yzc5MDo8XC9wPlxyXG5cclxuPHByZT5cclxuMTIzNDU2NzhcclxuKCkoKCkpKSk8XC9wcmU+XHJcblxyXG48cD4yXHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MCApXHViOTdjIChcdWI4NWMgXHVhY2UwXHVjZTY4XHVjNzNjXHViODVjXHVjMzY4IFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQ6PFwvcD5cclxuXHJcbjxwcmU+XHJcbjEyMzQ1Njc4XHJcbigoKCgpKSkpPFwvcHJlPlxyXG5cclxuPHA+XHViZTQ0XHVjMmI3XHVkNTU4XHVhYzhjLCA1XHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MCwgNlx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTAsIFx1ZDYzOVx1Yzc0MCA3XHViYzg4XHVjOWY4IFx1YmIzOFx1Yzc5MFx1Yjk3YyBcdWFjZTBcdWNlNjhcdWM3M2NcdWI4NWNcdWMzNjggXHVjNjJjXHViYzE0XHViOTc4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjU4NzUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUeXBvIiwiZGVzY3JpcHRpb24iOiI8cD5CZXNzaWUgaGFzIGp1c3QgcHVyY2hhc2VkIGEgbmV3IGxhcHRvcCBjb21wdXRlciwgYnV0IHNoZSB1bmZvcnR1bmF0ZWx5IGZpbmRzIGhlcnNlbGYgdW5hYmxlIHRvIHR5cGUgd2VsbCwgZ2l2ZW4gdGhlIHNpemUgb2YgaGVyIGxhcmdlIGhvb3ZlcyByZWxhdGl2ZSB0byB0aGUgc21hbGwga2V5Ym9hcmQuIEJlc3NpZSBoYXMganVzdCBhdHRlbXB0ZWQgdG8gdHlwZSBpbiBvbmUgb2YgaGVyIGZhdm9yaXRlIHBhdHRlcm5zIC0tIGEgYmFsYW5jZWQgc3RyaW5nIG9mIHBhcmVudGhlc2VzLiBIb3dldmVyLCBzaGUgcmVhbGl6ZXMgdGhhdCBzaGUgbWlnaHQgaGF2ZSBtaXMtdHlwZWQgb25lIGNoYXJhY3RlciwgYWNjaWRlbnRhbGx5IHJlcGxhY2luZyAoIHdpdGggKSBvciB2aWNlIHZlcnNhLiBQbGVhc2UgaGVscCBCZXNzaWUgY29tcHV0ZSB0aGUgbnVtYmVyIG9mIGxvY2F0aW9ucyBpbiB0aGUgc3RyaW5nIHN1Y2ggdGhhdCByZXZlcnNpbmcgdGhlIHNpbmdsZSBwYXJlbnRoZXNpcyBhdCB0aGF0IGxvY2F0aW9uIHdvdWxkIGNhdXNlIHRoZSBlbnRpcmUgc3RyaW5nIHRvIGJlY29tZSBiYWxhbmNlZC48XC9wPlxyXG5cclxuPHA+VGhlcmUgYXJlIHNldmVyYWwgd2F5cyB0byBkZWZpbmUgd2hhdCBpdCBtZWFucyBmb3IgYSBzdHJpbmcgb2YgcGFyZW50aGVzZXMgdG8gYmUgJnF1b3Q7YmFsYW5jZWQmcXVvdDsuIFBlcmhhcHMgdGhlIHNpbXBsZXN0IGRlZmluaXRpb24gaXMgdGhhdCB0aGVyZSBtdXN0IGJlIHRoZSBzYW1lIHRvdGFsIG51bWJlciBvZiAoJiMzOTtzIGFuZCApJiMzOTtzLCBhbmQgZm9yIGFueSBwcmVmaXggb2YgdGhlIHN0cmluZywgdGhlcmUgbXVzdCBiZSBhdCBsZWFzdCBhcyBtYW55ICgmIzM5O3MgYXMgKSYjMzk7cy4gRm9yIGV4YW1wbGUsIHRoZSBmb2xsb3dpbmcgc3RyaW5ncyBhcmUgYWxsIGJhbGFuY2VkOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPigpPFwvbGk+XHJcblx0PGxpPigoKSk8XC9saT5cclxuXHQ8bGk+KCkoKCkoKSk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD53aGlsZSB0aGVzZSBhcmUgbm90OjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPikoPFwvbGk+XHJcblx0PGxpPigpKSg8XC9saT5cclxuXHQ8bGk+KCgoKSkpKTxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzdHJpbmcgb2YgcGFyZW50aGVzZXMgb2YgbGVuZ3RoIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMDAsMDAwKS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaGUgbnVtYmVyIG9mIHBvc2l0aW9ucyB3aXRoaW4gdGhlIGlucHV0IHN0cmluZyAoaWYgYW55KSBzdWNoIHRoYXQgcmV2ZXJzaW5nIHRoZSBwYXJlbnRoZXNpcyBhdCB0aGF0IHNpbmdsZSBwb3NpdGlvbiB3b3VsZCBjYXVzZSB0aGUgZW50aXJlIHN0cmluZyB0byBiZWNvbWUgYmFsYW5jZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiPGg0Pk91dHB1dCBEZXRhaWxzPFwvaDQ+XHJcblxyXG48cD5JZiB3ZSBsb29rIGF0IHRoZSBpbnB1dCBzdHJpbmcgY2xvc2VseTo8XC9wPlxyXG5cclxuPHByZT4xMjM0NTY3OCBcclxuKCkoKCkpKSk8XC9wcmU+XHJcblxyXG48cD53ZSBmaW5kIHRoYXQgcmV2ZXJzaW5nIHRoZSBkaXJlY3Rpb24gb2YgdGhlIHBhcmVudGhlc2lzIGF0IHBvc2l0aW9uIDIgcmVzdWx0cyBpbiBhIGJhbGFuY2VkIHN0cmluZzo8XC9wPlxyXG5cclxuPHByZT4xMjM0NTY3OCBcclxuKCgoKCkpKSk8XC9wcmU+XHJcblxyXG48cD5TaW1pbGFybHksIHJldmVyc2luZyB0aGUgcGFyZW50aGVzaXMgYXQgcG9zaXRpb24gNSwgYXQgcG9zaXRpb24gNiwgb3IgYXQgcG9zaXRpb24gNywgYWxzbyByZXN1bHRzIGluIGEgYmFsYW5jZWQgc3RyaW5nLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > USA Computing Olympiad > 2012-2013 Season > USACO November 2012 Contest > Bronze 2번

  • 문제를 번역한 사람: kipa00
  • 문제의 오타를 찾은 사람: YunGoon