K = int(input())
if K==1:
print(0,1,end=" ")
else:
dp = [""]*(K+1)
dp[0] = "1"
dp[1] = "0"
for i in range(2,K+1):
dp[i] = dp[i-1] + dp[i-2]
final = dp[-1]
a_num = final.count("1")
b_num = final.count("0")
print(a_num,b_num,end=" ")
메모리 초과 이유
dp 배열을 문자열로 채운 것이 메모리 초과의 이유다. 문자열의 길이는 지수적으로 증가하기 때문에 K가 크면 매우 큰 문자열을 생성하게 되고, 이에 따라 메모리 사용량도 급격히 증가하된다
( 참고로, dp 배열은 피보나치 수열의 원리를 이용하여 이전 두 항을 결합하여 현재 항을 생성한다. 이때, dp 배열을 문자열로 채운다면 메모리 사용량도 급격히 증가한다. )
시도2) A의 갯수와 B의 갯수를 따로 계산
이를 해결하기 위해, 전체 문자열을 저장하지 않고 1의 개수와 0의 개수를 따로 계산할 수 있다!
K = int(input())
a_count=[0]*(K+1)
b_count=[0]*(K+1)
a_count[0] = 1 #0번 버튼 눌렀을 때, a의 갯수
b_count[0] = 0 #0번 버튼 눌렀을 때, b의 갯수
a_count[1] = 0 #1번 버튼 눌렀을 때, a의 갯수
b_count[1] = 1 #1번 버튼 눌렀을 때, b의 갯수
for i in range(2,K+1):
a_count[i] = a_count[i-1] + a_count[i-2]
b_count[i] = b_count[i-1] + b_count[i-2]
print(a_count[-1],b_count[-1],end=" ")