Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 해결하는 '연속된 1이 없는 음이 아닌 정수' 개수 구하기

양의 정수 n이 주어졌을 때, n 이하의 음이 아닌 정수 중에서 2진수 표현에 연속된 1이 포함되지 않는 수의 개수를 구하는 문제입니다. 예를 들어 입력이 7이라면 정답은 5가 됩니다. 5의 2진수 표현은 101로, 연속된 1이 나타나지 않기 때문입니다.

문제 접근 방법

이 문제는 다음 단계를 따라 해결할 수 있습니다.

  • 정수 n을 받아 2진수 문자열로 변환하는 convert() 함수를 정의합니다.
  • ret := 빈 문자열로 초기화합니다.
  • n이 0이 아닌 동안 다음을 반복합니다.
    • ret에 (n mod 2)를 추가합니다.
    • n을 오른쪽으로 1비트 시프트합니다.
  • ret을 반환합니다.
  • 메인 로직에서는 다음을 수행합니다.
  • bits := convert(num)의 호출 결과를 저장합니다.
  • n := bits의 길이로 설정합니다.
  • 길이가 n인 배열 ones와 zeroes를 선언합니다.
  • ones[0] := 1, zeroes[0] := 1로 초기화합니다.
  • i := 1부터 i < n까지 반복하며 다음을 수행합니다.
    • zeroes[i] := zeroes[i - 1] + ones[i - 1]
    • ones[i] := zeroes[i - 1]
  • ret := ones[n - 1] + zeroes[n - 1]로 설정합니다.
  • i := n - 2부터 i >= 0까지 역순으로 반복하며 다음을 수행합니다.
    • bits[i]가 '0'이고 bits[i + 1]도 '0'이면, ret에서 ones[i]를 뺍니다.
    • bits[i]가 '1'이고 bits[i + 1]도 '1'이면 반복문을 종료합니다.
  • ret을 반환합니다.

핵심 아이디어: 동적 계획법(DP)

배열 ones와 zeroes는 각각 길이가 i인 2진수 문자열 중 마지막 비트가 1 또는 0으로 끝나면서 연속된 1을 포함하지 않는 경우의 수를 의미합니다. 마지막 비트가 1이라면 그 앞 비트는 반드시 0이어야 하므로 ones[i] = zeroes[i - 1]이 되고, 마지막 비트가 0이라면 앞 비트는 0 또는 1 어느 쪽이든 가능하므로 zeroes[i] = zeroes[i - 1] + ones[i - 1]이 됩니다. 이는 피보나치 수열과 유사한 점화식을 따릅니다.

이후 실제 num의 2진수 표현과 비교하면서, num보다 작거나 같은 유효한 수만 남도록 결과를 보정합니다. 인접한 두 비트가 모두 '0'이면 해당 자리에서 1로 시작하는 경우들을 빼주고, 연속된 '1'이 발견되면 그 이상 유효한 수가 존재하지 않으므로 탐색을 중단합니다. 전체 시간 복잡도는 O(log n)으로 매우 효율적입니다.

구현 예시

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    string convert(int n){
        string ret = "";
        while(n){
            ret += (n % 2) + '0';
            n >>= 1;
        }
        return ret;
    }
    int findIntegers(int num) {
        string bits = convert(num);
        int n = bits.size();
        vector <int> ones(n);
        vector <int> zeroes(n);
        ones[0] = zeroes[0] = 1;
        for(int i = 1; i < n; i++){
            zeroes[i] = zeroes[i - 1] + ones[i - 1];
            ones[i] = zeroes[i - 1];
        }
        int ret = ones[n - 1] + zeroes[n - 1];
        for(int i = n - 2; i >= 0; i--){
            if(bits[i] == '0' && bits[i + 1] == '0') ret -= ones[i];
            else if(bits[i] == '1' && bits[i + 1]== '1') break;
        }
        return ret;
    }
};
main(){
    Solution ob;
    cout << (ob.findIntegers(7));
}

입력

7

출력

5