[python 파이썬] 백준 9625번 BABBA

www.acmicpc.net/problem/9625

9625번: BABBA

풀이1 - 시간초과

문제 읽고 어떤 유형인지 파악안하고 생각나는 대로 풀었다. 

제출해보니 시간초과가 나왔고 유형으로 접근해봐야겠다는 생각이 들었다. 

#9625번 BABBA

tmp='A'
k= int(input())
for i in range(k):
  new_tmp=''
  for j in tmp:
    if j=='A':
      new_tmp+='B'
    elif j=='B':
      new_tmp+='BA'
  tmp=new_tmp

cnt_A=0
cnt_B=0
for i in new_tmp:
  if i=='A':
    cnt_A+=1
  elif i =='B':
    cnt_B+=1

print(cnt_A,cnt_B)

 

풀이2 - 정답

이 문제는 피보나치, DP로 구현해야함을 깨달았다.

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

 

 

• 작은 것에서 큰 것으로 변하는 걸 봐서 DP or 피보나치임을 눈치채기 
• 문자열로 접근하지않고 문자의 개수로 접근하기