codewars: Count ones in a segment

문제 링크입니다: http://www.codewars.com/kata/count-ones-in-a-segment/train/cpp

4 KYU 문제다보니 완전탐색법으로 문제를 풀 경우 시간초과가 발생합니다.

따라서 이진수를 쭉 나열해보고 규칙을 찾아봤더니 비트를 사용하면 비교적 간단하게 풀 수 있는 문제였습니다!

물론 규칙을 찾아내는데 엄청 오랜 시간이 걸렸습니다.

/*

left와 right라는 숫자가 주어졌을 때(1 <= left, right <= 20000000000000000)

left와 right 사이의 숫자들을 이진수로 변환했을 때 1의 갯수의 합을 반환하시오

*/

#include <iostream>

#include <algorithm>

#include <bitset>

using namespace std;

 

//완전탐색법

/*

long long binary(int num)

{

        long long one = 0;

        while (num)

        {

               if (num % 2)

                       one++;

               num /= 2;

        }

        return one;

}

 

long long countOnes(int left, int right)

{

        long long sum = 0;

        for (long long i = left; i <= right; i++)

               sum += binary(i);

        return sum;

}

 

int main(void)

{

        cout << countOnes(4, 7) << endl;

        return 0;

}

*/

 

//코드에 대한 부연설명

// 이진수 자릿수: 3 2 1 0

// -----------------------

//  0             0 0 0 0

//  1             0 0 0 1

//  2             0 0 1 0

//  3             0 0 1 1

//  4             0 1 0 0

//  5             0 1 0 1

//  6             0 1 1 0

//  7             0 1 1 1

 

//위에 주어진 숫자에서

//0번째 자릿수를 가로로 눕히면 0 1 0 1 0 1 0 1

//1번째 자릿수를 가로로 눕히면 0 0 1 1 0 0 1 1

//따라서 7까지 0 번째 자릿수를 나열하면 (0 1)로 묶인 집합 네개

//반면 6까지 0 번째 자릿수를 나열하면 (0 1)로 묶인 집합 세개와 나머지 0

//즉 규칙은 0번째 자릿수에서는 (0 1)로 길이가 2

//1번째 자릿수에서는 (0 0 1 1)로 길이가 4

//2번째 자릿수에서는 (0 0 0 0 1 1 1 1)로 길이가 8

//... 즉 2^(자릿수+1)

 

//자릿수 세로줄을 반복하는대로 묶은 집합

long long pattern(long long num, int cipher) //num: 주어진 숫자, cipher: 자릿수

{

        long long bit = 1 << cipher; //bit는 2^(cipher)

        long long chain = num >> (cipher + 1); //규칙이 2^(자릿수 + 1)이므로

        return chain * bit;

}

 

//자릿수 세로줄을 반복하는대로 묶은 후 나머지

long long restOfBinary(long long num, int cipher)

{

        long long bit = 1 << cipher;

        long long rest = num % (bit << 1); //rest는 num % (bit * 2)

        return max((long long)0, rest - bit + 1);

}

 

long long column(long long num, int cipher) //cipher번째 자릿수의 합

{

        return pattern(num, cipher) + restOfBinary(num, cipher);

}

 

long long addUpTo(long long num)

{

        long long bit = 0, total = 0;

        while ((num >> bit) > 0) //자릿수가 존재할때까지 각 세로줄을 다 더한다

               total += column(num, bit++);

        return total;

}

 

long long countOnes(long long left, long long right)

{

        //addUpTo(right)-addUpTo(left-1) -> left~right

        return addUpTo(right) - addUpTo(left - 1);

}

 

int main(void)

{

        cout << countOnes(4, 7) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~