반응형
이진수
-
알고리즘: 백준 2193번 이친수 (feat.Python)알고리즘/백준(BaekJoon) 2020. 7. 29. 15:09
예시를 들어서 문제를 좀 더 자세히 뜯어 봅시다. f(N) = N 자리 이친수의 개수 라고 할때, N = 5 인 상태 즉, f(5)는 어떻게 구성되어 있을까요? 우선 N = 5 일때 이친수는 다음과 같습니다. 10101 10100 10010 10001 10000 이것들을 가장 처음 1을 제외한 그 다음 1을 기준으로 쪼개보면 다음과 하나의 규칙을 발견할 수 있습니다. 10101 10100 f(3)과 모양이 같고 100010 f(2)와 모양이 같고 100001 f(1)과 모양이 같습니다. 100000 N = 0 는 정의되어 있지는 않지만 f(0) = 1이라고 합시다. 이렇게 봤을 때 f(5) = f(3) + f(2) + f(1) + f(0) 이라고 할 수 있겠군요! 그런데 여기서 또 살펴보면 f(2) + ..