목록백준 2193번 (1)

하나씩 알아가기

[BOJ_2193] 이친수

n = int(input()) dp = [0 for _ in range(91)] dp[1] = 1 dp[2] = 1 for i in range(3, n+1): dp[i] = dp[i-2] + dp[i-1] print(dp[n]) 0으로 시작하지 않으면서 11을 부분 문자열로 갖지 않는 수를 이친수라 합니다. 일단 낮은 차수의 항들을 수동으로 구해줍시다. 1 2 3 4 1 10 100 101 1000 1010 1001 첫번째 두번째 항을 주목해 보면 한자리 수 이친수에 01을 붙이고 두자리 수 이친수에 0을 붙이면 101, 100으로 세자리 수의 이친수가 되는 것을 발견할 수 있습니다. 두자리 수 이친수에다가 01을 붙이고 세자리 수 이친수에 0을 붙이면 1001, 1000, 1010으로 네자리 수의 이친..
알고리즘 2021. 1. 25. 21:39
이전 Prev 1 Next 다음