9278번 - 절망적인 줄 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 77 | 38 | 34 | 49.275% |
문제
해빈시의 공원에는 화장실이 두 개가 있다. 그런데 그 중 하나가 얼마전에 고장났다. 이제 남은 건 한 개 뿐이다....
문제는 해빈이는 당장 화장실이 가고 싶은데, 화장실 앞의 줄이 매우 길다는 것이다!
고통을 잊기 위해 해빈이는 절망적인 줄을 쳐다보며 아래와 같은 문제를 풀기 시작했다.
화장실 사용료는 50원이다. 줄에 서 있는 사람들 중 반은 50원 동전을 가지고 있고, 나머지 반은 100원 동전만 가지고 있다.
화장실을 개장할 때, 관리인은 거슬러 줄 동전을 가지고 있지 않다.
100원 동전만 가진 사람에게는 50원 동전을 거슬러 줘야 한다. (이 경우, 50원 동전을 가진 사람이 먼저 등어가면서 지불한 동전을 거스름돈으로 사용한다)
사람들의 위치를 적절히 바꿔서 관리인의 거스름돈이 항상 모자라지 않게 하는 방법의 수를 구하라. 이때, 일부 사람들은 절대로 자리를 바꾸지 않는다. (뒤쪽, 앞쪽 모두 다)
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스는 길이가 n (1 ≤ n ≤ 1,000) 인 문자열 한 줄로 이루어져 있으며, 50원 동전을 가지고 있으면서 자리를 바꾸길 원치 않는 사람을 나타내는 '('와 100원 동전을 가지고 있으면서 자리를 바꾸길 원치 않는 사람을 나타내는 ')', 자리를 바꿔도 되는 사람을 나타내는 '.'으로 이루어져 있다.
'('와 ')'의 개수는 각각 n/2개 이하이고, n은 항상 짝수이다.
출력
각 테스트 케이스에 대해 문제의 조건을 지키며 자리를 바꿀 수 있는 방법의 수를 출력하라. 단, 문제의 답이 매우 커질 수 있으므로 마지막 여섯자리만 출력한다.
예제 입력 1
.... .(.. )... .....)......................
예제 출력 1
2 1 0 68484
출처
ICPC > Regionals > Europe > Central European Regional Contest > CTU Open Contest > CTU Open Contest, 2013 Q번
- 문제를 번역한 사람: WeissBlume
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호