[백준 9625] BABBA (DP)

문제

 

 

 

풀이

시도1)  메모리초과

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=" ")