#9625

결국은 풀지 못해서 도움을 받았다.
처음 생각했던 코드는 다음과 같다.

K = int(input())
ABstr= "A"

for i in range(0, K):
    ABList = list(ABstr)

    for j in range(0, len(ABList)):
        if ABList[j] == 'A':
            ABList[j] = 'B'
        elif ABList[j] == 'B':
            ABList[j] = 'BA'

    ABstr = ""

    for j in range(0, len(ABList)):
        ABstr += str(ABList[j])

cntA = cntB = 0
for i in range(0, len(ABstr)):
    if ABstr[i] == "A":
        cntA += 1
    if ABstr[i] == "B":
        cntB += 1

print(cntA, cntB)

답은 똑바로 나왔는데 시간 초과가 나왔다. 지금 생각해보면 너무나 당연했지만 왜 시간초과가 뜰거란 생각을 진작에 하지 못했을까

풀이 방법은 너무나 간단하다. list로 입력을 받고 해당 원소(A와 B)를 각각 규칙에 따라 바꿔주고 이를 다시 str로 합친다. 이를 또 다시 list로 바꿔서 주어진 K만큼 반복한다.

이 때 만들어지는 배열의 길이는 얼마일까?
(시간 복잡도로 생각해도 좋을 것 같다. 어차피 그 배열을 한바퀴 돌아야하니까)

K가 40 이라고 가정하고 모든 문자열이 B라고 했을 때 2^40 만큼이다.
=> B는 BA로 바뀌는데 그럼 배열의 길이가 2배가 되는 것이고 이를 읽을 땐 2배의 시간이 걸린다고 보면 된다.

한마디로 말도 안되는 시간이 걸린다. 이렇게 40분이라는 시간동안 삽질을 하고 있으니 옆에서 도움을 줬다.

문자열을 저장해놓을 필요가 없다. 뭔가 규칙이 있진 않을까 생각해봐라

그래서 무지성으로 일단 그려봤다.

규칙을 찾았다. 심지어 시간 복잡도는 O(K)이다. (입력값이 K라고 했을 때)

제일 처음 배열의 기본 값 list[0][0], list[0][1], list[0][2] 들을 저장해두고 반복문을 돌리기만 하면 주어진 값 K 까지의 값들이 전부 정해진다.

이런 생각을 할 수 있는 생각의 흐름은 다음과 같다.

1. 생성되는 문자열을 전부 저장해둬야 할까? 어차피 그 배열을 읽어서 A와 B의 개수를 세야 하는데 시간이 너무 길진 않을까?
2. K가 3이든 5든 10이든 K만 정해지면 답이 무조건 정해져 있다.
3. A와 B의 개수를 구하는 문젠데 A와 B의 순서가 중요할까? AAABB 와 AABBA의 경우 답은 똑같이 a=3, b=2 이다.

다음 부턴 이런 생각을 할 수 있었으면 좋겠다..

K = int(input()) + 1

answerList = []
for i in range(0,K):
    answerList.append([0,0,0])
# print(answerList)

answerList[0][0] = 1
answerList[0][1] = 0
answerList[0][2] = 1

for i in range(1, K):
    # print(i)
    answerList[i][0] = answerList[i-1][1]
    answerList[i][1] = answerList[i-1][2]
    answerList[i][2] = answerList[i][0] + answerList[i][1] 
    # print( answerList[i])

print(answerList[K-1][0], answerList[K-1][1])

시간 복잡도는 처음 값 3개 (list[0]) 를 지정해두면 그 다음부터는 값이 알아서 정해진다. list의 원소 하나가 원소를 3개 가지고 있다는 점을 무시하고 1차원 배열로 생각했을 때 list[1] 이 list[2]를 결정하고 list[2]가 list[3]을 결정한다. 처음부터 끝까지(입력값 K까지) 한번만 돌면서 값을 저장하면 되므로 시간 복잡도는 O(K)가 될 것이다.