Codeforces Round #739 (Div. 3)-D. Make a Power of Two

문제 설명

당신에게 정수 $n$이 주어진다. 우리는 다음 행동중에서 한가지를 선택해서 할 수 있다.

• 숫자에서 아무 자릿수를 지운다. (이 행동은 숫자가 1자리 일때에서 수행 가능하며 이 연산이 끝나면 숫자는 "공백"이다.)
• 한 자리 숫자를 맨 오른쪽에 붙인다.

이 행동은 마음대로 수행할 수 있고, 몇번이든 수행할 수 있다.

주의해야 할 점은 아무 자릿수를 지울때 0이 맨 앞으로 나올 수 있는데, 이 0은 지울 수 없다. 만약 숫자 $301$이 주어질 때, 숫자 $3$을 지우면 결과가 $01$가 된다. ($1$이 아니다.)

우리는 주어진 숫자에 최소 연산을 수행해서 2의 제곱수인 $2^k(k \ge 0)$로 만들어야 한다. 최종 결과로 나오는 수는 반드시 $0$이 맨 앞에 나오면 안된다.

예를 들어 $n = 1052$ 일때 답은 $2$이다.

1. 맨 뒤에 $4$를 추가한다. $(n = 10524)$
2. 숫자 $5$ 를 지운다.
   따라서 결과 값은 $1024$고 이 숫자는 2의 제곱수이다.

만약 $n = 8888$이면 답은 $3$이다. $8$을 3번 지우면 결과값이 $8$이고 이 수는 2의 제곱수이다.

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$ 이 주어진다.

각 테스트 케이스의 첫번째 줄에는 정수 $n (1 \le n \le 10^9)$ 가 주어진다.

Output
각 테스트케이스마다 2의 제곱수로 만들기 위해서 필요한 연산의 최소 개수인 $m$을 출력한다.

Example
input
12
1052
8888
6
75
128
1
301
12048
1504
6656
1000000000
687194767

output
2
3
1
3
0
0
2
1
3
4
9
2

문제 접근

사용한 알고리즘: 그리디, 구현, 문자열, 수학
걸린 시간 : 00:16
이 문제도! 그리디인걸 알았지만 구현이 안된다. 공책에 풀어서 sudo code를 거의 작성할때 바로 문제에 투입해야지 안그러면 코드 내부에서 디버깅하다가 시간 다 잡아먹는것 같다. 하나의 문자열을 다른 특정한 문자열로 바꿔야 하는 문제에서는 그리디한 접근법이 매우 도움이 된다는 것을 이 문제를 보고 유형을 알게됐다.

먼저 2의 배수를 만들어야 하기 때문에 2의 제곱수로 이루어진 문자열을 만들어야 한다. 그런데 여기서 1차적인 문제가 생긴가. 이 문자열을 어디까지 만들어야 할까? 문제에서는 주어지는 입력이 $10^9$ 즉 9자리까지라고 한다. 그런데 이것에 맞춰서 9자리 2의 제곱수까지 만들면 테스트 케이스가 답이 안 나올 것이다. 사실 왜 9자리의 2배인 18자리까지 필요한지는 잘 모르겠지만 내 생각은 다음과 같다.

9자리 숫자가 모두 맞지 않아서 싹다 갈아 엎어야 하는 경우 9개 숫자를 모두 지우고, 9개 숫자를 뒤에 계속 붙이면 되기 때문에 이 문제의 답은 최대 18이다. 그래서 18자리까지 확인을 해야하는 것 같다.

2의 제곱수를 만든 후에는 어떻게 문자열을 비교할까? 우리가 여기서 알아야 할 점은 문자열에서 아무 위치에 있는 수를 지울 수 있다는 것이다. 그런데 삽입하는 숫자는 무조건 맨 오른쪽이다. 그렇기 때문에 2의 제곱수 $k$와 주어진 수 $n$에서 공통된 수열을 찾되, 순서가 맞아야 한다. 그래야 공통되지 않은 문자를 삭제할 때, 남은 문자가 같을 것이다.

우리는 index를 두개 사용할 것이고, $a$는 $n$의 index, $b$는 $k$의 index이다. 우리의 기준은 $n$이기 때문에 모든 가능한 $k$중에서 다음 행동을 반복한다.

1. $a$와 $b$가 가르키는 문자열이 서로 같으면 $a$와 $b$모두 한칸 앞으로 움직인다.
2. $a$와 $b$가 가르키는 문자열이 서로 다르면 $a$만 한칸 앞으로 움직인다.

이 행위를 계속 반복하면 결국은 $a$가 끝까지 가게 된다. 그때 $b$의 위치로 값이 결정 된다. $b$가 $k$의 도중에 위치한다는 뜻은 $n$의 오른쪽 뒤에 $len(k) - b$개의 문자를 추가해야 한다는 뜻이다. 왜냐하면 $n$과 $k$에 공통된 문자열이 부족하다는 뜻이기 때문이다. 그리고 $b$의 앞에 있는 문자열은 둘이 공통된 문자열이기 때문에 $n$에서 공통되지 않은 문자열 $len(n) - b$개를 지워야한다. 따라서 우리가 해야할 연산은 $len(k) + len(n) - 2 \times b$ 이다. 그리고 모든 $k$에 대해서 이 값이 최소인 것이 답이다.

정답 코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    vector<string> p;
    for(long long i = 1; i <= 1e18; i*=2) p.push_back(to_string(i));
    int t; cin >> t;
    while(t--){
        string s; cin >> s;
        int ans = 987654321;
        for(int i = 0; i < p.size(); i++){
            int a = 0, b = 0;
            string st = p[i];
            while(a < s.size()){
                if(st[b] == s[a]){
                    a++;
                    b++;
                }else{
                    a++;
                }
            }
            ans = min(ans, (int)st.size() + (int)s.size() - 2 * b);
        }
        cout << ans << "\n";
    }
    return 0;
}