22039. 피보나치 수 분배 (SWEA)

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

출처:

SW Expert Academy

나의 풀이

T = int(input())

for test_case in range(1, T + 1):
    N=int(input())
    if N%3==1:
        print('impossible')
    elif N%3==2:
        print('BA'+'BBA'*(N//3))
    else:
        print('BBA'*(N//3))

• 피보나치 수열을 보면 1,1,2,3,5,8,13,21…이다.
• f(1)=f(2),f(3),f(4),f(5),f(6),f(7),f(8)…이고 f(1)=f(2),f(3),f(4),f(5)=f(3) + f(4),f(6),f(7),f(8)=f(6) + f(7)이므로 N을 나누었을 때 (f는 생략한다), 1,3,4,6,7/2,5,8 로 나눌 수 있다. 즉 BA+BBA*k의 형태가 된다.
• 3의 배수일 때는 1,2,4,5/3,6으로 나눌 수 있다. 따라서 BBA*k의 형태가 된다.