시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 44 29 28 70.000%

문제

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

)((()())())

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

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

입력

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

출력

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

예제 입력 1

)((()())())

예제 출력 1

4

힌트

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

  1. )()(())
  2. )()(())
  3. )()())(
  4. )()())(
W3sicHJvYmxlbV9pZCI6IjU4NzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWI5N2MgXHVjYzNlXHVjNTQ0XHViNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjOWNcdWJjMjlcdWM5YzBcdWNkOTUmbmJzcDtcdWJjYTBcdWMyZGMoXHVjMThjLCAxXHVjMTM4KVx1YjI5NCBcdWM2NzhcdWM1OTFcdWFjMDRcdWM3NDQgXHVkMGM4XHVjZDljXHVkNTc0XHVjMTFjIFx1ZDQ4MFx1Yjg1YyBcdWI0YTRcdWIzNmVcdWM3NzggXHVjMGIwXHViNGYxXHVjMTMxXHVjNzc0XHVjNWQwIFx1YzIyOFx1YzVjOFx1YjJlNC4gXHViMThkXHViZDgwXHVjNzc4IFx1Yzg3NFx1YzUyOFx1YjI5NCZuYnNwO1x1YmNhMFx1YzJkY1x1Yjk3YyBcdWIyZTRcdWMyZGMgXHVjN2ExXHVhZTMwXHVjNzA0XHVkNTc0IFx1YzYyOCBcdWQ0ODBcdWMyMzJcdWM3NDQgXHVjMGM1XHVjMGM1XHVkNzg4IFx1YjRhNFx1Yzg0Y1x1YzljMFx1YjljYyBcdWNjM2VcdWM5YzAgXHViYWJiXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHVhZGY4XHViMjk0Jm5ic3A7XHViY2EwXHVjMmRjXHViOTdjIFx1Y2MzZVx1YjI5NFx1YjM3MCBcdWM1YjRcdWI4MjRcdWM2Y2NcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM4NzRcdWM1ZDBcdWFjOGMmbmJzcDtcdWFkZjgmbmJzcDtcdWQ0ODBcdWJjMmRcdWM3NDAgTlx1YWMxY1x1Yzc1OCBcdWMxOGNcdWFkMDRcdWQ2MzhcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0Jm5ic3A7XHViYjM4XHVjNzkwXHVjNWY0XHVjYzk4XHViN2ZjIFx1YmNmNFx1YzYwMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPikoKCgpKCkpKCkpPFwvcD5cclxuXHJcbjxwPlx1Yzg3NFx1Yzc0MCBcdWJjYTBcdWMyZGNcdWM3NTggXHViNGI3XHViMmU0XHViOWFjXHVhYzAwJm5ic3A7XHVjNjdjXHVjYWJkIFx1YzE4Y1x1YWQwNFx1ZDYzOCBcdWI0NTAmbmJzcDtcdWFjMWNcdWFjMDAgXHViZDk5XHVjNWI0XHVjNzg4XHViMjk0IFx1YWM4MyAoKCZuYnNwO1x1YWNmYyZuYnNwO1x1YjYxMVx1YWMxOVx1Yzc3NCBcdWMwZGRcdWFlMzQgXHVhYzgzXHVjNzQ0IFx1YzU0Y1x1YWNlMFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YmNhMFx1YzJkY1x1Yzc1OCBcdWM1NWVcdWIyZTRcdWI5YWNcdWIyOTQgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzE4Y1x1YWQwNFx1ZDYzOCBcdWI0NTAgXHVhYzFjXHVhYzAwIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjI5NCBcdWFjODMgKSkmbmJzcDtcdWFjZmMgXHViNjExXHVhYzE5XHVjNzc0IFx1YzBkZFx1YWNiY1x1YjJlNC4gXHViY2EwXHVjMmRjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWI0YjdcdWIyZTRcdWI5YWNcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIHhcdWM3NzRcdWFjZTAgXHVjNTVlXHViMmU0XHViOWFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YWMwMCB5XHViNzdjXHVhY2UwIFx1ZDU2MFx1YjU0YyB4Jm5ic3A7Jmx0OyZuYnNwO3lcdWFjMDAgXHViNDE4XHViMjk0IFx1YzMwZFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjU0YywgXHViY2EwXHVjMmRjXHVhYzAwIFx1YzExY1x1Yzc4OFx1YjI5NCBcdWM3MDRcdWNlNThcdWFjMDAgXHViNDIwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMyMWNcdWMxMWNcdWMzMGRcdWI0ZTRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlYyBcdWM4NzRcdWM3NDQgXHViM2M0XHVjNjQwXHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzlmOFx1YzkwNFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YzE4Y1x1YWQwNFx1ZDYzOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMSAmbGU7IE4gJmxlOyA1MCwwMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YzlmOFx1YzkwNFx1YzVkMCBcdWJjYTBcdWMyZGNcdWFjMDAgXHVjMTFjXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjZTU4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIChcdWM5ODksICZuYnNwO1x1YWMwMCBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVhY2YzXHVjNzU4IFx1Yzc3OFx1YjM3MVx1YzJhNCZuYnNwO3hcdWM2NDAgXHVhYzAwIFx1YjA5OFx1ZDBjMFx1YjA5OFx1YjI5NCBcdWFjZjNcdWM3NTggXHVjNzc4XHViMzcxXHVjMmE0IHlcdWM1ZDBcdWMxMWMmbmJzcDt4Jmx0O3lcdWFjMDAgXHViNDE4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMjFjXHVjMTFjXHVjMzBkXHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuKTxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWMgXHViY2EwXHVjMmRjXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc0MCBcdWM1NDRcdWI3OThcdWM3NTggXHViMTI0XHVhYzAwXHVjOWMwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPikoKSgoKSk8XC9saT5cclxuXHQ8bGk+KSgpKCgpKTxcL2xpPlxyXG5cdDxsaT4pKCkoKSkoPFwvbGk+XHJcblx0PGxpPikoKSgpKSg8XC9saT5cclxuPFwvb2w+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTg3NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZpbmQgdGhlIENvdyEiLCJkZXNjcmlwdGlvbiI6IjxwPkJlc3NpZSB0aGUgY293IGhhcyBlc2NhcGVkIGFuZCBpcyBoaWRpbmcgb24gYSByaWRnZSBjb3ZlcmVkIHdpdGggdGFsbCBncmFzcy4gIEZhcm1lciBKb2huLCBpbiBhbiBhdHRlbXB0IHRvIHJlY2FwdHVyZSBCZXNzaWUsIGhhcyBkZWNpZGVkIHRvIGNyYXdsIHRocm91Z2ggdGhlIGdyYXNzIG9uIGhpcyBoYW5kcyBhbmQga25lZXMgc28gaGUgY2FuIGFwcHJvYWNoIHVuZGV0ZWN0ZWQuICBVbmZvcnR1bmF0ZWx5LCBoZSBpcyBoYXZpbmcgdHJvdWJsZSBzcG90dGluZyBCZXNzaWUgZnJvbSB0aGlzIHZhbnRhZ2UgcG9pbnQuIFRoZSBncmFzcyBpbiBmcm9udCBvZiBGYXJtZXIgSm9obiBsb29rcyBsaWtlIGEgc3RyaW5nIG9mIE4gKDEgJmx0Oz0gTiAmbHQ7PSA1MCwwMDApIHBhcmVudGhlc2VzOyBmb3IgZXhhbXBsZTo8XC9wPjxwPikoKCgpKCkpKCkpPFwvcD48cD5GYXJtZXIgSm9obiBrbm93cyB0aGF0IEJlc3NpZSZhcG9zO3MgaGluZCBsZWdzIGxvb2sganVzdCBsaWtlIGFuIGFkamFjZW50IHBhaXIgb2YgbGVmdCBwYXJlbnRoZXNlcyAoKCwgYW5kIHRoYXQgaGVyIGZyb250IGxlZ3MgbG9vayBleGFjdGx5IGxpa2UgYSBwYWlyIG9mIGFkamFjZW50IHJpZ2h0IHBhcmVudGhlc2VzICkpLiAgQmVzc2llJmFwb3M7cyBsb2NhdGlvbiBjYW4gdGhlcmVmb3JlIGJlIGRlc2NyaWJlZCBieSBhIHBhaXIgb2YgaW5kaWNlcyB4ICZsdDsgeSBzdWNoIHRoYXQgKCggaXMgZm91bmQgYXQgcG9zaXRpb24geCwgYW5kICkpIGlzIGZvdW5kIGF0IHBvc2l0aW9uIHkuICBQbGVhc2UgY29tcHV0ZSB0aGUgbnVtYmVyIG9mIGRpZmZlcmVudCBzdWNoIHBvc3NpYmxlIGxvY2F0aW9ucyBhdCB3aGljaCBCZXNzaWUgbWlnaHQgYmUgc3RhbmRpbmcuPFwvcD4iLCJpbnB1dCI6Ijx1bD48bGk+TGluZSAxOiBBIHN0cmluZyBvZiBwYXJlbnRoZXNlcyBvZiBsZW5ndGggTiAoMSAmbHQ7PSBOICZsdDs9IDUwLDAwMCkuPFwvbGk+PFwvdWw+Iiwib3V0cHV0IjoiPHVsPjxsaT5MaW5lIDE6IFRoZSBudW1iZXIgb2YgcG9zc2libGUgcG9zaXRpb25zIGF0IHdoaWNoIEJlc3NpZSBjYW4gYmUgc3RhbmRpbmcgLS0gdGhhdCBpcywgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBwYWlycyBvZiBpbmRpY2VzIHggJmx0OyB5IGF0IHdoaWNoIHRoZXJlIGlzIHRoZSBwYXR0ZXJuICgoIGF0IGluZGV4IHggYW5kIHRoZSBwYXR0ZXJuICkpIGF0IGluZGV4IHkuPFwvbGk+PFwvdWw+IiwiaGludCI6IjxoND5PdXRwdXQgRGV0YWlsczxcL2g0PjxwPlRoZXJlIGFyZSA0IHBvc3NpYmxlIGxvY2F0aW9ucyBmb3IgQmVzc2llLCBpbmRpY2F0ZWQgYmVsb3c6PFwvcD48cD4xLiApKCgoKSgpKSgpKSBeXiAgIF5ePFwvcD48cD4yLiApKCgoKSgpKSgpKSBeXiAgXl48XC9wPjxwPjMuICkoKCgpKCkpKCkpIF5eICAgICBeXjxcL3A+PHA+NC4gKSgoKCkoKSkoKSkgXl4gICAgICBeXjxcL3A+Iiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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