[BOJ #9625] BABBA

문제

상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다.

기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했다. 한 번 더 누르니 BA로 바뀌고, 그 다음에는 BAB, 그리고 BABBA로 바뀌었다. 상근이는 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다.

버튼을 K번 눌렀을 때, 화면에 A와 B의 개수는 몇 개가 될까?

 

입력

첫째 줄에 K (1 ≤ K ≤ 45)가 주어진다.

 

출력

첫째 줄에 A의 개수와 B의 개수를 공백으로 구분해 출력한다.

 

내가 쓴 코드 1 (틀림-시간초과)

K = int(input())
# B -> BA, A -> B
word = 'A'
while K:
    new = []
    for i in range(len(word)):
        if word[i] == 'A':
            new.append('B')
        else:
            new.append('BA')
    word = ''
    for n in new:
        word += n
    K -= 1
print(word)
A = word.count('A')
B = word.count('B')
print(A, B)

 

내가 쓴 코드 2 (맞.)

K = int(input())
# B -> BA, A -> B
A = 1
B = 0
for _ in range(K):
    new_A = 0
    new_B = 0
    if A:
        new_B = A
        A = 0
    if B:
        A += B
    B += new_B
print(A, B)

 

제출 결과

처음 제출한 건, A와 B의 개수를 출력 안하고 만든 문자열을 출력해서 틀렸고,

두번째는 출력만 고쳐서 제출했는데 시간초과가 나왔당..

그래서 아 이 로직이 아에 아니구나 싶어서 좀 더 생각해서, 문자열을 만드는 게 아니라 개수만 계산할 수 있게 코드를 작성하여 제출했다. 그러니 맞았다!! DP는 쓰지 않았다.. 나중에 언젠가 DP 공부를 할 때 다시 풀어보겠서...ㅎㅎ!