2716번 - 원숭이 매달기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 897 | 273 | 216 | 37.565% |
문제
깊은 아마존 정글에 거대한 나무들에서 갈색 원숭이들이 매우 좋아하는 무화과가 열리고, 이 나무에는 향나무노린재들이 서식하고 있다.
나무 꼭대기에 도달하기 위해서 원숭이들은 매우 조심스럽게 나무에 올라가는 길을 찾아야한다. 거대한 나무는 부서지기 쉬운 덩굴들이 있는데 이 덩굴들은 시소의 원리와 비슷하다. 덩굴의 무게가 불균형 하면 그 덩굴은 끊어지며 그 원숭이들은 땅으로 떨어져버린다. 원숭이들은 서로 협력하여 덩굴의 균형을 유지한다면 그들은 모두 무화과가 열리고 향나무노린재들이 서식하는 나무 꼭대기에 도달할 수 있다는 것을 발견했다.
덩굴은 두개의 덩굴로 나눠질 수 있는데 덩굴이 끊어지지 않기 위해서는 나눠진 두 덩굴은 같은 수의 원숭이들이 매달려 있어야한다. 덩굴의 나눠지는 지점을 "[]"로 정의 내리면 덩굴의 구조를 꺾쇠괄호로 표시할 수 있다. 또한 덩굴의 깊이는 25를 넘지 않는다.
원숭이들은 덩굴의 균형을 유지하면서 나무꼭대기에 도달할 수 있는 최소 원숭이 수를 알고 싶다. 나무 꼭대기에 도달하기 위해서 최소 한 마리 원숭이가 필요하다.
입력
첫째 줄에 테스트 케이스의 개수 N(1 ≤ N ≤ 1000)이 주어진다.
각 테스트 케이스는 한 줄로 이루어져 있고, 덩굴의 구조를 꺾쇠괄호로 표현한 문자열이 주어진다. 문자열의 길이는 0보다 크거나 같고, 150보다 작거나 같다.
출력
각 테스트 케이스마다 덩굴의 균형을 유지하면서 나무꼭대기에 도달할 수 있는 최소 원숭이 수를 출력한다.
예제 입력 1
3 [] [[][[]]]
예제 출력 1
2 1 8
힌트
예제 입력의 2번째 테스트 케이스는 빈 줄 입니다.
출처
ICPC > Regionals > North America > Greater New York Region > 2007 Greater New York Programming Contest F번
- 문제를 번역한 사람: baekjoon, Nada
- 잘못된 번역을 찾은 사람: hyakintoss
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호