728x90

 0. [C++] Kick Start 


https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050ff4/0000000000051183


 1. 풀이


조금 지저분한 코드가 나오긴 하였는데, 이 문제를 풀면서 포인트는 입력을 9진수라고 생각하고 입력을 받는 것이었다.


허나, 이것으로는 아직 부족한데, 바로 9의 배수도 고려를 해주어야 한다는 것이다.


이 수들을 공책에 써서 이리저리 굴려보니 9진수를 기준으로 9개씩 쌍을 나누어보면 1개의 9의 배수가 포함되는 것을 볼 수 있다.

이때, 이 배열에서 9의 배수 앞인지 뒤인지 판단은 ull n,m을 활용하였고, 1씩 더하여 9가 되는것이 빠른지 9의 배수가 더 빠르게 되는지 확인을 통해 체크하였다.


허나, 이 규칙은 1~8 구간에서 만족하질 못하는데, 이는 따로 예외처리를 해주어 만족시켜주었다.


이제 마지막으로 9진수로 들어왔다고 가정한 입력을 10진수로 변환을 하고, 그 수를 a,b로 주었고, 이 수 사이에 들어있는 9의 배수의 개수를 n,m이라 해주었다.


이제 return으로 (b-m) - (a-n) + 1을 해주면 완성!



 2. 소스코드


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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
 
typedef unsigned long long ull;
using namespace std;
 
bool stringMODNine(const string& S, int k) {
    int t = 0;
    for (int i = 0; i < S.size(); i++) {
        t += S[i] - 48;
    }
    t += k;
    if (t % 9 == 0)
        return true;
    else
        return false;
}
 
ull solve(const string& F, const string& L) {
 
 
    //10진수로 변환하자.
    ull a = 0, b = 0, c = 0;
    ull k = 1;
    for (int i = 1; i <= F.size(); i++) {
        a += (F[F.size() - i] - 48) * k;
        k *= 9;
    }
    k = 1;
    for (int i = 1; i <= L.size(); i++) {
        b += (L[L.size() - i] - 48) * k;
        k *= 9;
    }
    //사이에 중복되어있는 9의 배수의 개수를 찾자.(9개마다 1개가 포함)
    int arr[9];
    for (int i = 0; i < 9; i++) {
        arr[i] = i;
    }
    ull n = a, m = b;
    
    n /= 9;
    char x = F[F.size() - 1];
    bool flag = false;
    for (int i = 0; i < 9; i++) {
        
        if ((x - 48) == 9) {
            break;
        }
        if (stringMODNine(F, i)) {
            flag = true;
            break;
        }
        x++;
    }
    if (flag)
        n--;
    if (a == 8)
        n = 0;
        
    m /= 9;
    x = L[L.size() - 1];
    flag = false;
    for (int i = 0; i < 9; i++) {
        
        if ((x - 48) == 9) {
            break;
        }
        if (stringMODNine(L, i)) {
            flag = true;
            break;
        }
        x++;
    }
    if (flag)
        m--;
    if (b == 8)
        m = 0;
 
    
    //cout << a << " " << b << endl;
    //cout << n << " " << m << endl;
 
    return (b - m) - (a - n) + 1;
}
 
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    string F, L;
    
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> F >> L;
 
        cout << "Case #" << i << ": " << solve(F,L) << "\n";
    }
}
 
 
//void printNine(int N) {
//    int a = 9;
//    int count = 0;
//    for (int i = 1; i < N; i++) {
//        
//        if (includeNine(a)) {
//            count++;
//            cout << i << " : " << a << "\t\t" << count <<endl;
//        }
//            
//        a += 9;
//    }
//}
 
//
//ull seed[20];
//ull seedSum[20];
//
//bool includeNine(const ull& N) {
//    ull copy = N;
//    while (copy) {
//        int a = copy % 10;
//        if (a == 9)
//            return true;
//        copy /= 10;
//    }
//    return false;
//}
//
//ull nineFilter(const string& F, const string& L) {
//    ull count = 0;
//    ull a = atoi(F.c_str());
//    ull b = atoi(L.c_str());
//    ull i = a;
//    int temp = i % 9;
//    i += (9 - temp);
//    while (1) {
//        if (i > b)
//            break;
//        if (!includeNine(i))
//            count++;
//        i += 9;
//    }
//    return count;
//}
cs


 3. 참고




질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!




저작자표시

'<code jam> > |2018| kick start' 카테고리의 다른 글

[C++] Kick Start 2018 Round A - Scrambled Words(large dataset 시간초과)  (0) 2019.06.13
[C++] Kick Start 2018 Round A - Lucky Dip(나중에 다시)  (0) 2019.06.13

+ Recent posts

티스토리툴바