다이나믹 프로그래밍 알고리즘
Q
9625번: BABBA
상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했
www.acmicpc.net
A
다이나믹 프로그래밍을 이용하여 풀었다. 주의할 점은 문자열이기 때문에 단순히 풀면 메모리초과가 일어날 수 있다. A와 B가 각자 피보나치 수열을 따른다는 것을 이용하여 풀어야 한다.
코드
k = int(input()) #정수 입력
d = [0] * 46 #DP 테이블 초기화
d[0] = 0
d[1] = 1
c = [0] * 46 #DP 테이블 초기화
c[0] = 0
c[1] = 1
for i in range(2, k + 1):
d[i] = d[i-1] + d[i-2]
for j in range(2, k + 1):
c[j] = c[j-1] + c[j-2]
print(c[k - 1], d[k]) #메모리 초과를 피하기 위해 A와 B를 나누어서 만들었다.
메모리 초과로 틀렸던 코드
k = int(input())
d = [0] * 46
d[0] = 'A'
d[1] = 'B'
for i in range(2, k + 1):
d[i] = d[i-1] + d[i-2]
print(d[k].count('A'), d[k].count('B'))
