COCI 2018/2019 결선 문제 2번- 미녀와 야수 > 문제은행 : 정보올림피아드&알고리즘




3401 : 미녀와 야수

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
3 회   
시도횟수
28 회   

문제

미녀와 야수는 요즘 유행하는 인기 TV 쇼의 제목이다. 

이 TV 쇼에서 게스트로 초대된 미녀 영화배우는, 깊이가 N인 이진 트리 미로에 갇힌다. 

게스트는 이진 트리의 루트 노드(정점)에서 시작하여, 출구가 있는 리프(자식이 없는 노드)까지 걸어가며,이 모습이 생중계되는 방식이다. 

각 리프 노드에는 출구가 있으며, 출구 밖에는 야수가 있을 수도 있고, 동현, 딧불, 건우 등의 유명 남배우들이 대기하고 있을 수도 있다.


이진 트리의 각 노드는 고유한 번호가 있으며, 루트 노드가 1번이고, 각 노드 X의 왼쪽 자식은 2X, 오른쪽 자식은 2X + 1의 번호를 가지고 있다.


사실 우리의 미녀 게스트는, 방송 특성상 몇 번째 방에서 어느 방향으로 가야 하는지를 이미 지령 받은 상태로 시작한다. 

첫 번째 방에서는 왼쪽, 두 번째 방에서는 오른쪽… 이런 식으로 말이다. 

 

문제는 불쌍한 게스트가 “왼쪽”이 어느 방향이고 “오른쪽”이 어느 방향인지 헷갈려 한다는 것이다. 

여러분이 게스트라고 상상해 보자. 

트리 구조대로라면 트리의 왼쪽 자식이 왼쪽 방향이겠지만, (그림1)

게스트가 노드 위에 서서 자식 노드 방향으로 앞을 바라보면, 오른쪽 자식이 왼쪽으로 보일 것이다. (그림 2)

그림1

그림 2​


그래서 게스트는 진행 도중에 K번, 그림 1처럼 트리 구조대로 좌우를 판단할지, 아니면 그림 2처럼 자기 시선에서 좌우를 판단할지에 관하여 마음을 바꾼다. 

마음의 변화는 각 노드에서 최대 한 번씩만 일어난다. 

시작하자마자 루트 노드에서 마음을 바꿀 수도 있다. 

TV쇼 시작 전에는, 게스트의 마음(방향감각)이 그림 1과 같은 트리 구조 기준일 수도 있고, 그림 2와 같은 자기 시선 기준일수도 있다.


미남 배우들은 리프 노드 중, 그 번호가 A이상 B이하인 노드에 있다. 

미녀 게스트가 정확히 K번 마음을 바꿔서 갈 수 있는 리프 노드 중, A이상 B이하인 노드의 번호의 합을 출력하는 프로그램을 작성하라. 

답이 클 수 있으므로, 10억 7로 나눈 나머지를 출력한다. 


입력형식

첫 줄에 N과 K가 공백을 사이에 두고 주어진다. N은 트리의 깊이(루트에서 리프까지의 노드 개수)이고, K는 게스트가 마음을 바꾸는 횟수이다.(2≤N≤1,000 , 0≤K≤N-1) 

둘째 줄에 N-1개의 문자로 이루어진 문자열이 들어온다. 문자는 ‘L’ 또는 ‘R’이며, 앞에서부터 각 갈림길에서 미녀가 지령 받은 방향을 나타낸다. L은 왼쪽, R은 오른쪽을 나타낸다. 

셋째 줄에 A가 2진수로 주어지며, 맨 앞자리는 1이다. 

넷째 줄에 B가 2진수로 주어지며, 맨 앞자리는 1이다. 

 

 

부분문제의 제약 형식 


부분문제 1: 전체 100점 중 8점에 해당하며 K=0이다. 

부분문제 2: 전체 100점 중 14점에 해당하며 N≤25이다. 

부분문제 3: 전체 100점 중 17점에 해당하며, A는 가장 왼쪽에 있는 리프 노드, B는 가장 오른쪽에 있는 리프 노드이다. 

부분문제 4: 전체 100점 중 61점에 해당하며, 주어진 제약 외 아무 제약 조건이 없다.


출력형식

게스트가 도달할 수 있는 A이상 B이하의 리프 노드의 번호의 총합을 1,000,000,007로 나눈 나머지를 출력한다.

입력 예

3 0
LR
101
110

출력 예

11

입력 예

4 2
LRR
1010
1110

출력 예

37

입력 예

5 2
RLLR
10010
10111

출력 예

82

Hint!

예시 1에서 게스트는 마음을 바꾸지는 않지만, 처음 입장하기 전에 방향감각이 두 가지가 있을 수 있다. 따라서 (이진 트리 기준(그림 1 방향감각)으로) L, R과 R, L의 두 가지 경우가 있으며, 각각 노드 5와 6에 도달하여 합이 11이 된다.

 

예시 2에서 A, B값에 상관없이 리프 노드에 도달가능한 경로는 6가지가 있다. (루트 노드에 입장하자마자 마음을 바꿀 수 있음을 유의한다.): (L,L,L) (L,L,R) (L,R,L) (R,L,R) (R,R,L) (R,R,R)




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP