백준 9625번 바로가기

첫 번째 풀이

txt = "A"
for _ in range(int(input())):
  txt = txt.replace("A","*").replace("B","BA").replace("*","B")
print(txt.count("A"), txt.count("B"))

메모리 초과 에러 발생…

두 번째 풀이

a,b = 1,0
for _ in range(int(input())):
  a,b = b,a+b
print(a,b)

CODE REVIEW

  1. 역시 DP(Dynamic Programming)을 이용해야만 풀 수 있는 문제였다. 규칙을 찾아서 풀어내보자.
  2. 한 번 시행할 때마다, A -> B / B -> BA로 바뀌기 때문에 a의 갯수 -> b의 갯수 / b의 갯수 -> a+b의 갯수가 된다.