Problem D 풀이 (C++)

 문제 링크 : https://codeforces.com/contest/1560/problem/D

숫자 n의 최댓값은 10억이다.

따라서 10자리의 숫자는 10억 한 개, 나머지 중 가장 높은 자릿수를 가지는 숫자는 최대 9자리 숫자이다.

9자리 숫자가 최대한 높은 자리의 2^k인 수를 만드는 경우는 9자리에 계속 숫자를 붙이는 경우다.

9자리 숫자에서 최대 움직임 수는 9자리 숫자 모두 지운 후 하나의 수를 붙여 총 10번 움직이는 것이다.

9자리 숫자가 아무리 많이 움직여야 하는 숫자라도 최대 10번이라는 것이다.

그러므로 만약 9자리 숫자에 숫자를 10번 붙이거나 9자리 숫자를 다 지우고 하나 붙여서 10번 작업하는 것 두 가지의 경우 아무거나 상관없으므로

9자리 수에 최대한 많이 붙여지는 경우의 2^k의 자릿수는 18자리가 최대이다.


2^k인 수 중 18자리인 수들까지의 숫자의 개수는 총 59개이다.

그렇기 때문에 이 59개의 수들을 모두 구해놓고 숫자 n과 59개의 수를 비교하여 가장 적은 횟수로 만들어지는 경우를 찾는다.

각 숫자와 비교하여 만들어지는 횟수를 찾는 방법은 다음과 같다.


2^k인 수를 x라 하자.

x의 가장 높은 자리의 숫자부터 차례대로 n에 존재하는지 확인한다.

n을 탐색할 때 가장 높은 자리부터 탐색해 나간다.

존재한다면 x의 바로 다음 자리의 숫자를 탐색하고 이 방식대로 x의 모든 숫자를 탐색한다.

탐색하다가  n의 모든 숫자의 순회가 끝나게 되면 이 과정은 끝나게 된다.

이때 x의 모든 숫자가 n에 포함되어 있지 않을 수 있고

가장 높은 자리의 숫자부터 임의의 개수의 숫자가 포함되어 있을 것이다.

모든 탐색이 끝났을 때 n에서 x를 구성하는 숫자와 순서에 맞게 일치하는 숫자의 개수를 알 수 있다.

이 개수를 num이라고 할 때,

n을 구성하고 있는 숫자의 개수 - num 개수가 지워야 하는 숫자의 개수이고

x를 구성하고 있는 숫자의 개수 - num 개수가 붙여야 하는 숫자의 개수이다.

그러므로 n에서 x를 만들기 위해 실행해야 할 작업의 총개수는

( n을 구성하는 숫자의 개수 - num ) + ( x를 구성하는 숫자의 개수 - num ) 이 된다.


n에서 탐색할 때 x를 구성하는 순서에 맞게 높은 자리부터 차례대로 탐색하는 이유는,

n에서 x를 만들 때 중간의 숫자를 제거할 수는 있지만 새로운 숫자를 추가할 때는 무조건 오른쪽에 붙여야 하기 때문이다.

만약 x를 구성하는 숫자들과 일치하는 숫자를 n에서 뽑았는데 숫자들의 순서가 x의 순서와 같지만

x의 가장 높은 자리부터 차례대로 이어지지 않고 도중에 숫자 사이에 없는 숫자가 있다면 

n에서 x를 만들 때 중간에 숫자를 넣을 수 없기 때문에 x를 만들 수 없다.


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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int main() {
 
    string nums[60];
    long long init = 1;
 
    for (int i = 0; i < 60; i++) {
        nums[i] = to_string(init);
        init *= 2;
    }
 
    int t;
    cin >> t;
 
    while (t--) {
 
        string n;
        cin >> n;
 
        int ans = 11;
 
        for (auto num : nums) {
            
            int count = 0;
 
            int idx = 0;
 
            for (int i = 0; i < num.length(); i++) {
 
                bool isNum = false;
 
                for (int j = idx; j < n.length(); j++) {
                    if (num[i] == n[j]) {
                        count++;
                        idx = j + 1;
                        isNum = true;
                        break;
                    }
                }
 
                if (isNum == false)
                    break;
            }
 
 
            if (ans > (n.length() - count) + (num.length() - count))
                ans = (n.length() - count) + (num.length() - count);
        }
 
        cout << ans << endl;
    }
 
    return 0;
}
cs

댓글

댓글 쓰기