Codeforces Round #739 (Div. 3) Problem. D (After contest)

https://codeforces.com/contest/1560/problem/D
Codeforces Round #739 (Div. 3)

D. Make a Power of Two

TimeLimit	MemoryLimit	Difficulty	Tags
1 S	256 MB	1300	greedy math strings

Attr	SubNo	SolveTime	Time	Memory	Accept?
-1	126372797	TIME OVER	233 ms	3700KB	Accepted(Late)

---

문제 요약

2의 제곱으로 만들어라.

정수 n이 주어지고, 다음과 같은 행동을 할 수 있다.

• 임의의 숫자 하나를 지울 수 있다 (만약 숫자가 하나밖에 남지 않았으면 “empty”가 된다)
• 오른쪽에 숫자 하나를 놓을 수 있다.

가장 왼쪽에 0이 있을 때, 0은 지워지지 않는다.
예시) 301에서 3을 빼면, 1이 아닌 01이 된다

최소한의 행동만 하여 n을 2의 제곱으로 만들어라.

피드백

Input

1-st line : Testcase (1 <= t <= 10⁴)
각 Testcase 마다
t-th line : 1개의 정수 (1 <= n <= 10⁹)

Output

각 Testcase 마다
1개의 정수 m : 2의 제곱으로 만드는 최소 비용

---

문제 풀이

처음엔 햇갈렸지만, 결국 string을 사용하여 노가다로 풀 수 있는 문제라는 사실을 깨닳았다.

하나의 문자를 구현하기 위해서는 구현할 문자와 비교해가면서 필요없는 숫자는 빼고, 필요한 숫자만 마지막에 더해주면 쉽게 구현을 할 수 있다.(비용은 언제나 최소비용이 든다)

또한 n의 최대 범위가 10의 9승이기 때문에, 아무리 비용이 많이 들어도 9 이상으로는 들지 않을 것이다.
10의 9승 이하에서 모든 값을 지우고 1만 추가하면 최대 9의 비용이 나온다

처음엔 long long int의 최대 범위를 10의 19승까지 했지만, 잘못된 선택이였다.

long long int의 범위를 잘못 알고 있었었다. 이부분에서 시간을 많이 잡아먹었다
결국 long long int의 범위 문제였고, 범위를 10의 18승으로 줄여 문제를 해결했다.

---

최종 해설

먼저 간단한 예외(n이 이미 2의 제곱일때)는 미리 검사하고 걸러냈다.

만약 그렇지 않으면, n을 string으로 바꿔서 시작한다.

그 뒤로 2의 제곱을 계속해서 비교해 가면서 최소비용을 계산을 한다.
만약 비용이 1이 나오면, 1보다 작은 비용은 나오지 않기 때문에 검사를 종료하였다.

검사는 n의 digit들을 하나씩 돌아가면서 구현할 숫자와 비교를 한다.
n과 다른 숫자가 있으면 해당 digit를 제거하고, n의 탐색이 먼저 끝나면 남은 digit들을 추가해주면 구현이 완료된다.

n의 최대값은 10⁹이므로 가장 큰 최소 비용은 9가 된다.
10의 9승 이하에서 모든 값을 지우고 1만 추가하면 최대 9의 비용이 나온다
그러므로 +-를 계산하여 구현해볼 최대의 2의 제곱수는 10¹⁸ 까지 확인을 해 주었다.

---

최종 코드

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
 
using namespace std;
 
bool CheckPow(int a) {
    while(a > 1) {
        if(a % 2) return false;
        a/=2;
    }
    return true;
}
 
long long int Power(long long int a, long long int b) {
    long long int result = a;
    for(long long int i = 1; i < b; i++) 
        result = result * a;
    return result;
}
 
int main(void) {
    int TestCase = 0;
    cin >> TestCase;
    while (TestCase --)
    {
        int n;
        cin >> n;
        if(CheckPow(n)) {
            cout << 0 << endl;
            continue;
        }
        string num = to_string(n);
        long long int now = 1;
        int result = 15;
        int weight = 9;
        //cout << (long long int)powl(10, 20) << endl;
        //cout << Power(10, 18) << endl;
        while (result > 1 && now < Power(10, 18)) {
            string nstr = to_string(now);
            int i = 0, j = 0;
            int trash = 0;
            for(i = 0; i < nstr.length(); i++) {
                for(j; j < num.length(); j++) {
                    if(nstr[i] == num[j]) 
                        break;
                    trash++;
                }
                if(j==num.length()) {
                    trash += nstr.length() - i;
                    break;
                }
                else j++;
            }
            result = min(result, trash + (int)(num.length()-j));
 
            now *= 2;
        }
        cout << result << endl;
    }
    
    return 0;
}

느낀점

처음 봤을 때 막막했지만, 오랜시간 고민해본 결과 해법을 알아내고 시간은 얼마 남지 않았었다.
결국 오류를 잡지 못하고 대회가 종료되고 말았다.

결국 int의 범위 때문에 큰 오류가 났었는데, 다음부턴 최대값을 정하고 작업을 하는게 안전할 것 같다.