Problem B 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1520/problem/B

ordinary인 수가 어떻게 분포되어 있을지 생각해 보면

1 ~ 9 => 1, 2, 3, 4 ~~, 9 = 9개

10 ~ 99 => 11, 22, 33, 44, ~~, 99 = 9개

100 ~ 999 => 111, 222, 333, 444, ~~, 999 = 9개

.

.

.

이런 식으로 분포되어 있다.

n이 x 자리의 수라면, x보다 하나 낮은 자리까지 ordinary인 수를 모두 가지고 있기 때문에

기본적으로 9 * (x - 1)개를 가진다.

x 자리의 ordinary인 수를 알기 위해서는 n의 가장 높은 자리의 숫자 a를 확인하고

숫자 a로만 구성되어 있는 x 자리의 수보다 n이 작으면 a - 1개,

크거나 같다면 a개라는 것을 알 수 있다.

결국 답은 9 * (x - 1) + a개 또는 9 * (x - 1) + a - 1개가 된다.


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
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
 
        int n;
        cin >> n;
 
        vector<int> v;
 
        int num = n;
        while (num != 0) {
            v.push_back(num % 10);
            num /= 10;
        }
 
        int a = v[v.size() - 1];
        int check = 0;
        for (int i = 0; i < v.size(); i++) {
            check += a;
            a *= 10;
        }
 
        int ans = 9 * (v.size() - 1) + v[v.size() - 1];
 
        if (check <= n)
            cout << ans << endl;
        else
            cout << ans - 1 << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기