2963번 - 무한 이진 트리 탐색 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 479 | 121 | 92 | 31.724% |
문제
다음과 같은 세가지 성질을 갖는 트리를 무한 이진 트리라고 한다.
- 모든 노드는 두 개의 자식 노드를 가지고 있다. 왼쪽 노드, 오른쪽 노드
- 어떤 노드의 번호가 X라면, 왼쪽 자식 노드의 번호는 2*X, 오른쪽 자식 노드의 번호는 2*X+1이다.
- 루트의 번호는 1이다.
무한 이진 트리를 탐색할 때는, 루트에서 시작한다. 그리고, 왼쪽 자식 또는 오른쪽 자식으로 이동하거나, 현재 노드에서 그대로 있을 수 있다.
탐색은 'L','R','P'로 이루어진 문자열로 표현할 수 있다.
- 'L': 왼쪽 자식으로 이동
- 'R': 오른쪽 자식으로 이동
- 'P': 현재 노드에 그대로 있음
탐색의 값은 마지막으로 방문한 노드의 번호이다. 예를 들어, LR의 값은 5이고, RPP의 값은 3이다.
탐색의 집합은 'L','R','P','*'로 이루어진 문자열로 표현할 수 있다. '*'는 3개중 그 어떤 것이 될 수 있다.
탐색의 집합은 문자열과 일치하는 모든 패턴을 포함한다.
예를 들어, L*R은 LLR, LRR, LPR이며, **은 LL,LR,LP,RL,RR,RP,PL,PR,PP이다.
마지막으로, 탐색의 집합의 값은 탐색의 집합에 포함되어 있는 모든 탐색의 값의 합이다.
탐색의 집합의 문자열이 주어졌을 때, 탐색의 집합의 합을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 탐색의 집합의 문자열이 주어진다. 이 문자열은 'L','R','P','*'로만 이루어져 있으며, 길이가 최대 10,000이다.
출력
첫째 줄에 탐색의 집합의 합을 출력한다.
예제 입력 1
P*P
예제 출력 1
6
예제 입력 2
L*R
예제 출력 2
25
예제 입력 3
**
예제 출력 3
33
예제 입력 4
LLLLLRRRRRLLLLLRRRRRLLLLLRRRRRLLLLL
예제 출력 4
35400942560
출처
Contest > Croatian Open Competition in Informatics > COCI 2008/2009 > Contest #2 5번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호