백준 22478번: FizzBuzz [C++]

작성일 | In
플래티넘 V 플래티넘 V

문제

FizzBuzz

$3$의 배수일때는 Fizz, $5$의 배수일때는 Buzz, 둘 모두의 배수일때는 FizzBuzz, 그 외에는 수 자신을 나열해서 얻은 문자열을 FizzBuzz String이라 합시다. 이는 아래와 같이 나타납니다.

12Fizz4BuzzFizz78…

위와 같은 FizzBuzz String에서 $s$번째 문자부터 $20$개의 문자를 출력하는 문제입니다.

풀이

우리는 $s$번째 문자가 포함된 수를 찾고 싶습니다.

이 수를 $n$이라 합시다.

$i$부터 $j$까지 FizzBuzz String에서 차지하는 문자의 개수를 계산하려고 할 때, $i$부터 $j$까지 자릿수가 일치하면 쉽게 계산할 수 있습니다.

자릿수를 $k$라 하면 $k(j - i + 1)$에서 $3$의 배수의 개수만큼 $(4 - k)$를 더하고, $5$의 배수의 개수만큼 $(4 - k)$를 더한 다음 $15$의 배수의 개수만큼 $k$를 더해주면 됩니다.

따라서 먼저 $n$의 자릿수를 구해 줍시다.

모든 한 자리 수가 FizzBuzz String에서 차지하는 문자의 개수의 합이 $s$보다 작다면 이를 $s$에서 뺍니다.

모든 두 자리 수가 FizzBuzz Stirng에서 차지하는 문자의 개수의 합이 $s$보다 작다면 또 이를 $s$에서 뺍니다.

모든 $k$자리 수가 FizzBuzz String에서 차지하는 문자의 개수의 합이 $s$보다 크거나 같을 때 까지 이를 반복합니다.

그렇게 찾은 $n$의 자릿수는 $k$가 됩니다.

이제 같은 계산법으로 이분 탐색을 통해서 $n$을 찾으면 됩니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(_) ((void)0)
#endif
using namespace std;

using ll = long long;

ll power(ll base, ll exp) {
    ll ret = 1;

    while (exp) {
        if (exp & 1)
            ret *= base;
        base *= base;
        exp >>= 1;
    }

    return ret;
}

ll getMultipleCnt(ll start, ll end, ll base) {
    ll c = 0;

    while (start <= end and start % base != 1) {
        if (start % base == 0)
            c++;
        start++;
    }

    return c + (end - start + 1) / base;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll s;
    cin >> s;

    ll lo = 1;
    ll digit = 1;
    while (true) {
        ll cnt = digit * 9 * power(10, digit - 1);
        cnt += (4 - digit) * getMultipleCnt(lo, 10 * lo - 1, 3);
        cnt += (4 - digit) * getMultipleCnt(lo, 10 * lo - 1, 5);
        cnt += digit * getMultipleCnt(lo, 10 * lo - 1, 15);

        if (s <= cnt)
            break;

        s -= cnt;
        lo *= 10;
        digit++;
    }

    ll hi = lo * 10 - 1;
    while (lo < hi) {
        ll mid = (lo + hi) / 2;

        ll cnt = digit * (mid - lo + 1);
        cnt += (4 - digit) * getMultipleCnt(lo, mid, 3);
        cnt += (4 - digit) * getMultipleCnt(lo, mid, 5);
        cnt += digit * getMultipleCnt(lo, mid, 15);

        if (s <= cnt)
            hi = mid;
        else {
            lo = mid + 1;
            s -= cnt;
        }
    }

    string str;
    for (int i = 0; i < 20; i++) {
        if (lo % 3 == 0 and lo % 5 == 0)
            str.append("FizzBuzz");
        else if (lo % 3 == 0)
            str.append("Fizz");
        else if (lo % 5 == 0)
            str.append("Buzz");
        else
            str.append(to_string(lo));
        lo++;
    }

    for (int i = 0; i < 20; i++)
        print("{}", str[s + i - 1]);

    return 0;
}

백준 22478번: FizzBuzz [C++]