일렬로 꾸미기(Linear Garden) > 문제은행



문제은행

1509 : 일렬로 꾸미기(Linear Garden)

제한시간: 1000 ms    메모리제한: 128 MB
해결횟수: 17 회    시도횟수: 110 회   



람세스 2세가 전투에서 승리를 거두고 귀환했다. 

그는 승리를 기리기 위해 웅장한 정원을 조성하기로 결심했다. 

그래서 궁궐이 있는 Lubrr에서부터 시작해 Karnak 신전에 이르는 긴 길을 따라 식물을 일렬로 쭉 심을 예정이다. 

심는 식물은 연꽃(L)과 파피루스(P) 이렇게 단 두 종류이다. 

이들은 각각 이집트 북부와 남부의 상징이기 때문이다.

 

정원에는 그런 식으로 N개의 식물을 심는데, 종류별 식물 배치에 균형이 있어야 한다. 

정원 내부의 어느 구간(연속적인)이라도 양 종류의 식물의 개수 차이가 2를 넘어서는 안 된다.

 

람세스가 세우고자 하는 정원은 L 아니면 P로 이루어진 문자열로 나타낼 수 있다. 

예를 들어 N=5인 경우 위에서 제시한 균형을 갖춘 정원은 14가지가 있을 수 있다. 

(LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, PPLPL)

 

그리고 특정 길이에 대해 균형을 갖춘 정원 식물 배치를 나타내는 문자열들은 알파벳 오름차순으로 나열하여 1부터 번호를 매길 수 있다. 

가령 N=5의 경우, 12번에 해당하는 정원 문자열은 PLPPL이다.

 

길이가 N인 균형 잡힌 정원을 나타내는 어떤 문자열을 입력 받아 이것이 그 길이에 해당하는 전체 균형 잡힌 정원 문자열 중 오름차순으로 몇째 순서에 해당하는지 서열을 구하고, 이 값을 어떤 정수 M으로 나눈 나머지를 출력하는 프로그램을 작성하시오.

 

단, 이 M이라는 수는 문제 풀이를 더 쉽게 해 주기 위해 있는 것으로, 다른 의미는 없음을 밝힌다.

 




첫째 줄에는 정원에 일렬로 심을 식물의 수 N이 있다. (1≤N≤1,000,000)
둘째 줄에는 정수 M이 있다. (7≤M≤10,000,000)
셋째 줄에는 균형 잡힌 정원을 나타내는 문자열이 있다. 길이가 N이며 모든 문자는 L(연꽃) 아니면 P(파피루스)로만 구성되어 있다.



0 이상 M-1 이하의 범위에 있는 정수 하나를 출력한다.
입력 파일에 들어있는 정원 문자열의 오름차순 서열을 M으로 나눈 나머지의 값이다.


5 
7 
PLPPL
5


12
10000
LPLLPLPPLPLL
39






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.