유사 칸토어 비트열

문제 설명

수학에서 칸토어 집합은 0과 1 사이의 실수로 이루어진 집합으로, [0, 1]부터 시작하여 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만들어집니다.

 

남아는 칸토어 집합을 조금 변형하여 유사 칸토어 비트열을 만들었습니다. 유사 칸토어 비트열은 다음과 같이 정의됩니다.

 

0 번째 유사 칸토어 비트열은 "1" 입니다.

n(1 ≤ n) 번째 유사 칸토어 비트열은 n - 1 번째 유사 칸토어 비트열에서의 1을 11011로 치환하고 0을 00000로 치환하여 만듭니다.

남아는 n 번째 유사 칸토어 비트열에서 특정 구간 내의 1의 개수가 몇 개인지 궁금해졌습니다.

n과 1의 개수가 몇 개인지 알고 싶은 구간을 나타내는 l, r이 주어졌을 때 그 구간 내의 1의 개수를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ n ≤ 20
• 1 ≤ l, r ≤ 5n
• l ≤ r < l + 10,000,000
• l과 r은 비트열에서의 인덱스(1-base)이며 폐구간 [l, r]을 나타냅니다.

입출력 예

n	l	r	result
2	4	17	8

---

문제 해설

 

이건 코딩테스트가 아니라 IQ테스트 라고 이해해도 될 정도로 코드작성능력과 별개의 능력을 요구한다.

 

조건을 나열해보자.

• 비트열이 1이 나올 때 에는 11011 로 배열을 만든다.
• 비트열이 0 이 나타나면 00000 로 배열을 만든다.
• n번째 비트열은, 비트열을 만드는 과정을 n번 반복한다는 의미
• 배열의 임의의 구간에서 1의 개수를 리턴하라.

즉, 조건항에 따라 배열을 새롭게 생성하고, 해당 배열 내부에서 값을 가져오라는 의미인데 이건 코딩문제에 따른 프로그래밍 능력을 평가하는게 아니라

 

일정 규칙 내에서 가장 효율적이지만, 이질적인 프로그래밍을 하도록 결과를 유도한다.

 

그대로 값을 기입해서 출력하게 되면 시간초과로 실패한다.

---

첫 번째 시도

#include <string>
#include <vector>

using namespace std;

int solution(int n, long long l, long long r) {
    int answer = 0;
    vector<bool> canto(1);
    canto[0] = true;

    for (int i = 0; i < n; i++)
    {
        vector<bool> next;
        next.reserve(canto.size() * 5);
        for (bool def : canto)
        {
            if (def)
                next.insert(next.end(), { true, true, false, true, true });
            else
                next.insert(next.end(), { false, false, false, false, false });
        }
        canto = next;
    }
    for (long long i = l-1; i < r; ++i) {
        answer += canto[i];
    }
    return answer;
}

실패

 

코드 작성상 동작사항은 올바르나, 시간초과가 나타난다.

 

값을 나열하는 객체를 reserve로 조정하든 객체를 다른식으로 재정의하든 상관없이 배열을 참조하기위해 배열을 생성한다는 발상을 하는순간 실패하게 만들었다.

 

악질이다.

 

---

두 번째 시도

#include <string>
#include <vector>

using namespace std;

bool isOne(long long idx) {
    while (idx > 0) {
        if (idx % 5 == 2) {
            return false;
        }
        idx /= 5;
    }
    return true;
}

int solution(int n, long long l, long long r) {
    long long count = 0;
    for (long long i = l; i <= r; ++i) {
        if (isOne(i - 1)) {
            count++;
        }
    }
    return count;
}

성공

 

배열을 만든다는 과정에 도달할 수 없다!

 

그럼으로 배열이 생성되는 규칙성을 살펴보아야 하는데, 쉽게 이해해보자.

 

 

값은 항상 11011 이 반복되는것을 알 수 있다. 그렇다면, 11011 에서 11011 이 어떤식으로 반복되는지 나타내면 다음과 같다.

 

1101111011000001101111011 이다.

여기에서 0의 위치를 살펴보면 규칙성을 살펴볼 수 있다.

1	1	0	1	1	1	1	0	1	1
0	1	2	3	4	5	6	7	8	9

 

그렇다! 0은 항상 5로 나누었을때 나머지값이 2가 나오는 값으로 나타나게 된다!

 

그래서, if문으로 데이터를 돌린 다음 5의 나머지값이 2가 나오면 0임으로 더하지 않는다.

나머지값이 2가 아니라면 1임으로 1을 더해준다.

 

이걸 l과 r사이값만큼 돌려주면 결과가 나타난다.