문자열 피보나치 > 문제은행



문제은행

1390 : 문자열 피보나치

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



0과 1의 비트로 구성된 문자열 피보나치의 정의는 다음과 같다.

F(N) = 0 (N == 0)
F(N) = 1 (N == 1)
F(N) = F(N - 1) + F(N - 2) (N >= 2)

문자열 피보나치의 정의에서 ‘ + ’ 는 아래 예시와 같이 문자열을 이어 붙이는 것이다.

<예시>

e3050b66a1b29a01767400d7560a4131_1449744
 


N 과 비트 패턴 P 가 주어질 때, F(N)에서 패턴 P 가 몇 번 나오는지 구하는 프로그램을 작성하시오.


첫 행에 정수 N( 0≤N≤100 ) 이 주어진다. 다음 행에 비트 패턴 P 가 주어진다. 이러한 형식으로 여러 개의 테스트 케이스(5개 이하)가 입력될 수 있다. 입력의 마지막은 파일의 끝으로 한다. 패턴 P 에는 적어도 하나의 비트가 존재하며 길이는 100,000 이하이다.



각 테스트 케이스에 대하여 패턴 P 가 F(N) 에 몇 번 나오는지 아래 예제와 같은 형식으로 출력하시오.
F(N)에서 패턴 P 는 겹쳐질 수 있다. 나올 수 있는 경우의 수는 263 이하이다.


6
10
7
10
6
01
6
101
96
10110101101101
Case 1: 5
Case 2: 8
Case 3: 4
Case 4: 4
Case 5: 7540113804746346428






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