600. Non-negative Integers without Consecutive Ones

[zeikar]

Problem link

https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/

Problem Summary

n 이하의 수 중에서 2진법으로 했을 때 1이 연속으로 나오지 않는 수의 개수를 구하는 문제.

Solution

DP로 풀 수 있다.

특정 자리 수에서 1이 연속으로 나오지 않는 수의 개수는 DP로 구하고 n보다 작은지 판단은 1이 나왔을 때 0으로 시작하는 나머지 수들을 더해주면 된다.

아래 디스커션이 이해하기 좋다.
https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/discuss/1363063/C%2B%2BPython-DP-on-32-Bits-Clear-explanation-Clean-and-Concise-O(1)

Source Code

from functools import lru_cache


class Solution:
    def findIntegers(self, n: int) -> int:

        @lru_cache(None)
        def solve(digits, end):
            if digits == 0:
                return 1

            if end == 0:
                return solve(digits - 1, 0) + solve(digits - 1, 1)
            else:
                return solve(digits - 1, 0)

        result = 0
        binary = bin(n)[2:]
        prev = '0'

        for i in range(len(binary)):
            if binary[i] == '1':
                result += solve(len(binary) - i - 1, 0)

                # 11
                if prev == '1':
                    return result
            prev = binary[i]

        return result + 1