이번 문제는 다이나믹 프로그래밍을 통해 해결할 수 있는 문제이다. 점화식을 구한 뒤에 각 계산의 결과를 담아두는 배열에 저장하여 이를 반환한다.

• k를 입력받는다.
• 계산 결과를 담아 둘 배열 ansA, ansB를 선언한다.
• 초기의 상태는 'A'이므로 ansA[0]=1, ansB[0]=0이다.
• 점화식을 구한다.
  -> A, B, BA, BAB, BABBA, ...
  -> (ansA, ansB) = (1,0), (0,1), (1, 1), (1, 2), (2, 3), ...
  -> 문자열에서의 B가 BA가 되고, A는 B가 되므로 결과적으로 다음 문자열에서의 A의 갯수는 이전 문자열에서의 B의 갯수가 된다.
  -> 문자열에서의 A가 B가 되고, B는 BA가 되므로 결과적으로 다음 문자열에서의 B의 갯수는 이전 문자열에서의 A의 갯수와 B의 갯수를 합친 값이 된다.
  -> ansA[i] = ansB[i-1]
  -> ansB[i] = ansA[i-1] + ansB[i-1]
• 구한 점화식을 k만큼 for문에서 반복하여 ansA와 ansB를 채운다.
• ansA와 ansB의 k번째 값을 출력한다.

Code

k=int(input())
ansA = [0]*(k+1)
ansB = [0]*(k+1)
ansA[0]=1
for i in range(1, k+1):
    ansA[i]=ansB[i-1]
    ansB[i]=ansA[i-1]+ansB[i-1]
print(ansA[k], ansB[k])