코드를 보여드리게 앞서서

어떤 방식에 착안해 풀었는지 설명 드리겠습니다.


0세대를 FX, 0'세대를 YF 라 했을 때,

1세대는 (FX)+(YF) (0세대 + 0'세대) ##편의상 괄호로 묶었습니다. ##

2세대는 (FX+YF)+(FX-YF) (1세대+1'세대) ##FX-YF 를 1'세대라고 가정했습니다. 이때, 1'세대는 0세대 - 0'세대로 구성됨을 알 수 있습니다. ##

이때 3세대 문자열은

2세대+2'세대가 된다는 것을 알고


N세대 문자열을 gen(N)이라 했을 때

gen(N) = gen(N-1) + gen(N-1') ( + 로 연결됨)

N'세대 문자열은

gen(N') = gen(N-1) - gen(N-1') ( - 로 연결됨) 가 성립함에 착안해서 아래 링크와 같이 코드를 작성했습니다.


(링크 들어가셔서 스크롤 내려야 보입니다.)

http://colorscripter.com/s/BBQ9AnK 


이때 제가 궁금한점은 제가 짠 위 solve 함수의 시간복잡도입니다.

n 세대의 solve 함수 호출에서

n-1세대의 2개 호출로 나눠지는 경우는 52번째 줄 뿐이고,

대부분의 경우에서 n-1세대의 2개 호출이 아닌 1개 호출을 하는데

이럴 때는 시간복잡도를 어떻게 계산해야 하나요?...