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

문제

천방지축 베시(소, 1세)는 외양간을 탈출해서 풀로 뒤덮인 산등성이에 숨었다. 농부인 존씨는 베시를 다시 잡기위해 온 풀숲을 샅샅히 뒤졌지만 찾지 못하였다. 안타깝게도 그는 베시를 찾는데 어려워하고 있다. 존에게 그 풀밭은 N개의 소괄호로 이루어진 문자열처럼 보였기 때문이다. 예를 들면, 아래와 같다.

)((()())())

존은 베시의 뒷다리가 왼쪽 소괄호 두 개가 붙어있는 것 (( 과 똑같이 생긴 것을 알고있다. 또한 베시의 앞다리는 오른쪽 소괄호 두 개가 붙어있는 것 )) 과 똑같이 생겼다. 베시의 위치는 뒷다리의 위치가 x이고 앞다리의 위치가 y라고 할때 x < y가 되는 쌍으로 표현될 수 있다.

이때, 베시가 서있는 위치가 될 수 있는 서로 다른 순서쌍들의 개수를 구하여 존을 도와보자.

입력

첫 째줄에 N개의 소괄호로 이루어진 문자열이 주어진다. (1 ≤ N ≤ 50,000)

출력

첫 째줄에 베시가 서있을 수 있는 위치의 개수를 출력한다. (즉,  가 나타나는 곳의 인덱스 x와 가 나타나는 곳의 인덱스 y에서 x<y가 되는 서로 다른 순서쌍들의 개수를 출력한다.)

예제 입력 1

)((()())())

예제 출력 1

4

힌트

예제에서 베시가 있을 수 있는 곳은 아래의 네가지이다.

  1. )()(())
  2. )()(())
  3. )()())(
  4. )()())(
W3sicHJvYmxlbV9pZCI6IjU4NzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWI5N2MgXHVjYzNlXHVjNTQ0XHViNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjOWNcdWJjMjlcdWM5YzBcdWNkOTUmbmJzcDtcdWJjYTBcdWMyZGMoXHVjMThjLCAxXHVjMTM4KVx1YjI5NCBcdWM2NzhcdWM1OTFcdWFjMDRcdWM3NDQgXHVkMGM4XHVjZDljXHVkNTc0XHVjMTFjIFx1ZDQ4MFx1Yjg1YyBcdWI0YTRcdWIzNmVcdWM3NzggXHVjMGIwXHViNGYxXHVjMTMxXHVjNzc0XHVjNWQwIFx1YzIyOFx1YzVjOFx1YjJlNC4gXHViMThkXHViZDgwXHVjNzc4IFx1Yzg3NFx1YzUyOFx1YjI5NCZuYnNwO1x1YmNhMFx1YzJkY1x1Yjk3YyBcdWIyZTRcdWMyZGMgXHVjN2ExXHVhZTMwXHVjNzA0XHVkNTc0IFx1YzYyOCBcdWQ0ODBcdWMyMzJcdWM3NDQgXHVjMGM1XHVjMGM1XHVkNzg4IFx1YjRhNFx1Yzg0Y1x1YzljMFx1YjljYyBcdWNjM2VcdWM5YzAgXHViYWJiXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHVhZGY4XHViMjk0Jm5ic3A7XHViY2EwXHVjMmRjXHViOTdjIFx1Y2MzZVx1YjI5NFx1YjM3MCBcdWM1YjRcdWI4MjRcdWM2Y2NcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM4NzRcdWM1ZDBcdWFjOGMmbmJzcDtcdWFkZjgmbmJzcDtcdWQ0ODBcdWJjMmRcdWM3NDAgTlx1YWMxY1x1Yzc1OCBcdWMxOGNcdWFkMDRcdWQ2MzhcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0Jm5ic3A7XHViYjM4XHVjNzkwXHVjNWY0XHVjYzk4XHViN2ZjIFx1YmNmNFx1YzYwMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPikoKCgpKCkpKCkpPFwvcD5cclxuXHJcbjxwPlx1Yzg3NFx1Yzc0MCBcdWJjYTBcdWMyZGNcdWM3NTggXHViNGI3XHViMmU0XHViOWFjXHVhYzAwJm5ic3A7XHVjNjdjXHVjYWJkIFx1YzE4Y1x1YWQwNFx1ZDYzOCBcdWI0NTAmbmJzcDtcdWFjMWNcdWFjMDAgXHViZDk5XHVjNWI0XHVjNzg4XHViMjk0IFx1YWM4MyAoKCZuYnNwO1x1YWNmYyZuYnNwO1x1YjYxMVx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFlMzQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWNlMFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YmNhMFx1YzJkY1x1Yzc1OCBcdWM1NWVcdWIyZTRcdWI5YWNcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzE4Y1x1YWQwNFx1ZDYzOCBcdWI0NTAgXHVhYzFjXHVhYzAwIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjI5NCBcdWFjODMgKSkmbmJzcDtcdWFjZmMgXHViNjExXHVhYzE5XHVjNzc0IFx1YzBkZFx1YWNiY1x1YjJlNC4gXHViY2EwXHVjMmRjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWI0YjdcdWIyZTRcdWI5YWNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIHhcdWM3NzRcdWFjZTAgXHVjNTVlXHViMmU0XHViOWFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCB5XHViNzdjXHVhY2UwIFx1ZDU2MFx1YjU0YyB4Jm5ic3A7Jmx0OyZuYnNwO3lcdWFjMDAgXHViNDE4XHViMjk0IFx1YzMwZFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjLCBcdWJjYTBcdWMyZGNcdWFjMDAgXHVjMTFjXHVjNzg4XHViMjk0IFx1YzcwNFx1Y2U1OFx1YWMwMCBcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzIxY1x1YzExY1x1YzMwZFx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNWVjIFx1Yzg3NFx1Yzc0NCBcdWIzYzRcdWM2NDBcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOWY4XHVjOTA0XHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjMThjXHVhZDA0XHVkNjM4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygxICZsZTsgTiAmbGU7IDUwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOWY4XHVjOTA0XHVjNWQwIFx1YmNhMFx1YzJkY1x1YWMwMCBcdWMxMWNcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1Yzk4OSwgJm5ic3A7XHVhYzAwIFx1YjA5OFx1ZDBjMFx1YjA5OFx1YjI5NCBcdWFjZjNcdWM3NTggXHVjNzc4XHViMzcxXHVjMmE0Jm5ic3A7eFx1YzY0MCBcdWFjMDAgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1YWNmM1x1Yzc1OCBcdWM3NzhcdWIzNzFcdWMyYTQgeVx1YzVkMFx1YzExYyZuYnNwO3gmbHQ7eVx1YWMwMCBcdWI0MThcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMyMWNcdWMxMWNcdWMzMGRcdWI0ZTRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4pPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxY1x1YzVkMFx1YzExYyBcdWJjYTBcdWMyZGNcdWFjMDAgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzQwIFx1YzU0NFx1Yjc5OFx1Yzc1OCBcdWIxMjRcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+KSgpKCgpKTxcL2xpPlxyXG5cdDxsaT4pKCkoKCkpPFwvbGk+XHJcblx0PGxpPikoKSgpKSg8XC9saT5cclxuXHQ8bGk+KSgpKCkpKDxcL2xpPlxyXG48XC9vbD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1ODc0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmluZCB0aGUgQ293ISIsImRlc2NyaXB0aW9uIjoiPHA+QmVzc2llIHRoZSBjb3cgaGFzIGVzY2FwZWQgYW5kIGlzIGhpZGluZyBvbiBhIHJpZGdlIGNvdmVyZWQgd2l0aCB0YWxsIGdyYXNzLiAgRmFybWVyIEpvaG4sIGluIGFuIGF0dGVtcHQgdG8gcmVjYXB0dXJlIEJlc3NpZSwgaGFzIGRlY2lkZWQgdG8gY3Jhd2wgdGhyb3VnaCB0aGUgZ3Jhc3Mgb24gaGlzIGhhbmRzIGFuZCBrbmVlcyBzbyBoZSBjYW4gYXBwcm9hY2ggdW5kZXRlY3RlZC4gIFVuZm9ydHVuYXRlbHksIGhlIGlzIGhhdmluZyB0cm91YmxlIHNwb3R0aW5nIEJlc3NpZSBmcm9tIHRoaXMgdmFudGFnZSBwb2ludC4gVGhlIGdyYXNzIGluIGZyb250IG9mIEZhcm1lciBKb2huIGxvb2tzIGxpa2UgYSBzdHJpbmcgb2YgTiAoMSAmbHQ7PSBOICZsdDs9IDUwLDAwMCkgcGFyZW50aGVzZXM7IGZvciBleGFtcGxlOjxcL3A+PHA+KSgoKCkoKSkoKSk8XC9wPjxwPkZhcm1lciBKb2huIGtub3dzIHRoYXQgQmVzc2llJmFwb3M7cyBoaW5kIGxlZ3MgbG9vayBqdXN0IGxpa2UgYW4gYWRqYWNlbnQgcGFpciBvZiBsZWZ0IHBhcmVudGhlc2VzICgoLCBhbmQgdGhhdCBoZXIgZnJvbnQgbGVncyBsb29rIGV4YWN0bHkgbGlrZSBhIHBhaXIgb2YgYWRqYWNlbnQgcmlnaHQgcGFyZW50aGVzZXMgKSkuICBCZXNzaWUmYXBvcztzIGxvY2F0aW9uIGNhbiB0aGVyZWZvcmUgYmUgZGVzY3JpYmVkIGJ5IGEgcGFpciBvZiBpbmRpY2VzIHggJmx0OyB5IHN1Y2ggdGhhdCAoKCBpcyBmb3VuZCBhdCBwb3NpdGlvbiB4LCBhbmQgKSkgaXMgZm91bmQgYXQgcG9zaXRpb24geS4gIFBsZWFzZSBjb21wdXRlIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHN1Y2ggcG9zc2libGUgbG9jYXRpb25zIGF0IHdoaWNoIEJlc3NpZSBtaWdodCBiZSBzdGFuZGluZy48XC9wPiIsImlucHV0IjoiPHVsPjxsaT5MaW5lIDE6IEEgc3RyaW5nIG9mIHBhcmVudGhlc2VzIG9mIGxlbmd0aCBOICgxICZsdDs9IE4gJmx0Oz0gNTAsMDAwKS48XC9saT48XC91bD4iLCJvdXRwdXQiOiI8dWw+PGxpPkxpbmUgMTogVGhlIG51bWJlciBvZiBwb3NzaWJsZSBwb3NpdGlvbnMgYXQgd2hpY2ggQmVzc2llIGNhbiBiZSBzdGFuZGluZyAtLSB0aGF0IGlzLCB0aGUgbnVtYmVyIG9mIGRpc3RpbmN0IHBhaXJzIG9mIGluZGljZXMgeCAmbHQ7IHkgYXQgd2hpY2ggdGhlcmUgaXMgdGhlIHBhdHRlcm4gKCggYXQgaW5kZXggeCBhbmQgdGhlIHBhdHRlcm4gKSkgYXQgaW5kZXggeS48XC9saT48XC91bD4iLCJoaW50IjoiPGg0Pk91dHB1dCBEZXRhaWxzPFwvaDQ+PHA+VGhlcmUgYXJlIDQgcG9zc2libGUgbG9jYXRpb25zIGZvciBCZXNzaWUsIGluZGljYXRlZCBiZWxvdzo8XC9wPjxwPjEuICkoKCgpKCkpKCkpIF5eICAgXl48XC9wPjxwPjIuICkoKCgpKCkpKCkpIF5eICBeXjxcL3A+PHA+My4gKSgoKCkoKSkoKSkgXl4gICAgIF5ePFwvcD48cD40LiApKCgoKSgpKSgpKSBeXiAgICAgIF5ePFwvcD4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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