"Numbers On a Tree"

다음은 문제 "Numbers On a Tree"의 한국어 번역입니다:

시간 제한: 1초
메모리 제한: 256 MB
제출: 5232
정답: 2041
맞힌 사람: 1743
정답 비율: 39.189%

문제
Lovisa는 KTH에서 Stefan Nilsson 교수의 완전 이진 트리에 대한 강의를 듣고 있습니다. "완전 이진 트리에는 루트라고 불리는 특별한 노드가 있으며, 보통 맨 위에 그려집니다. 최하위 층의 노드들(잎이라고 부릅니다)을 제외한 모든 노드는 두 개의 자식 노드를 가집니다." Lovisa는 이미 이 모든 것을 알고 있어서 약간 지루해합니다. 이를 눈치챈 Stefan은 Lovisa에게 새로운 도전 과제를 제시합니다.

먼저, 우리는 완전 이진 트리의 노드에 다음과 같이 번호를 매깁니다. 오른쪽 맨 아래 잎에서 시작하여 1번을 부여하고, 같은 레벨의 노드들에 오른쪽에서 왼쪽으로 증가하는 순서로 번호를 매깁니다. 한 레벨을 끝내면 바로 위 레벨의 가장 오른쪽 노드로 이동하여 그 레벨의 모든 노드에 오른쪽에서 왼쪽으로 번호를 매깁니다. 이런 방식으로 루트에 도달할 때까지 계속합니다.

트리의 노드를 설명하고자 할 때, 우리는 루트에서 시작하여 잎 방향으로 내려가는 경로를 설명함으로써 할 수 있습니다. 각 비-잎 노드에서 우리는 왼쪽('L') 또는 오른쪽('R')으로 갈 수 있습니다.

그림 A.1: 높이가 3인 레이블이 붙은 이진 트리와 루트에서 시작하는 두 개의 표시된 경로. 경로 LR은 레이블 11로 이어지고 경로 RRL은 2로 이어집니다. 루트의 번호는 15입니다.

Lovisa의 과제는 트리의 높이 H와 루트에서 시작하는 경로 설명이 주어졌을 때 해당 노드의 레이블을 계산하는 것입니다.

입력
입력의 유일한 줄에는 트리의 높이 H (1 ≤ H ≤ 30)와 'L'과 'R' 문자로 구성된 문자열이 포함되어 있습니다. 이 문자열은 루트에서 시작하는 트리 내 경로를 나타냅니다. 문자 'L'은 왼쪽 자식을 선택하는 것을, 'R'은 오른쪽 자식을 선택하는 것을 의미합니다. 경로 설명은 비어 있을 수 있으며 최대 H개의 문자로 이루어집니다.

출력
주어진 경로에 해당하는 노드의 레이블을 포함하는 한 줄을 출력하세요.

예제 입력 1

3 LR

예제 출력 1

11

예제 입력 2

3 RRL

예제 출력 2

2

예제 입력 3

2

예제 출력 3

7

출처
Contest > KTH Challenge > KTH Challenge 2014 A번

• 문제를 만든 사람: Lukáš Poláček

알고리즘 분류

• 수학
• 트리