[백준 1078] 뒤집음

1078번: 뒤집음

문제 풀이

어려운 수학적 문제이다. 여러 과정을 통해 상수 시간에 가까운 풀이를 얻었다.

이 글은 풀이를 얻기 위해 어떠한 생각을 거쳤는지 설명하는 글이다.

D가 9의 배수가 아닐 경우 만족하는 x가 없음 증명

x = $ a_{0}10^{n-1} + a_{1}10^{n-1} + ... + a_{n-1}10^0 $

x를 뒤집은 수 = $ a_{n-1}10^{n-1} + a_{n-2}10^{n-1} + ... + a_{0}10^0 $

x - (x를 뒤집은 수) = $ a_{0}(10^{n-1}-10^0) + a_{1}(10^{n-2}-10^1) + ... $ 이다.

$ (10^n-10^m) \equiv 0 $ $ (mod 9) $ $ (n, m \geq 0) $가 항상 성립하므로, x - (x를 뒤집은 수)는 무조건 9의 배수이다.

그렇다면 D가 9의 배수이면 무조건 만족하는 x가 있을까? 정답은 No 이다. 이유는 밑에서 설명하겠다.

관찰력으로 얻은 사실

위에서 얻은 식 $ a_{0}(10^{n-1}-10^0) + a_{1}(10^{n-2}-10^1) + ... $ 에서 N이 5일 때를 예로 들자.

$ a_{0}(10^4-10^0) + a_{1}(10^3-10^1) + a_{2}(10^2-10^2) + a_{3}(10^1-10^3) + a_{4}(10^0-10^4) $

$ = 9999(a_{0}-a_{4}) + 990(a_{1}-a_{3}) $ 이다. 이 식을 잘 관찰해 두 가지 아이디어를 얻었다.

첫 번째는 $ -9 \leq a_{i}-a_{j} \leq 9 $가 항상 성립하기 때문에, D를 얻기 위해 그리디적으로 접근해도 된다는 사실이다.

예를 들어 D = 9999인 다섯자리 X를 찾는다고 하자. 그러면 무조건 $ a_{0}-a_{4} $는 1이어야 한다. 0이 된다면 뒤의 수에서 9999로 채울 수 없다.

이는 일반화가 가능하다. 이유는 위 식의 계수가 $(10^n-10^m)$, $(10^{n-1}-10^{m+1})$ 순서로 작아지고,
$10^n-10^m \geq 10 \times (10^{n-1}-10^{m+1})$ 이기 때문이다.

여기까지 이해된다면 왜 D가 9의 배수일 때 무조건 만족하는 x가 없는지도 이해될 것이다.

두 번째는 $ -9 \leq a_{i}-a_{j} \leq 9 $이고, $ (a_{i},a_{j}) $ 조합은 x를 작게 만들기 위해 한정지을 수 있다는 점이다.

예를 들어 52894나 10070이나 똑같은 D값을 갖는데, 오른쪽 수가 훨씬 작다.

아래 표는 X를 가장 작게 만들기 위한 $(a_{i},a_{j})$ 값이다. 여기서 주의사항은 0일 때이다.
만약 $a_{0}-a_{n-1}$이 0일 때 (0,0)으로 채우면 맨 앞이 0이 와버린다. 그러므로 이 때만 예외로 (1,1)로 채운다.

$a_{i}-a_{j}$	$(a_{i},a_{j})$
-9	(0,9)
-8	(0,8)
-7...	(0,7)
0	(0,0),(1,1)
...7	(7,0)
8	(8,0)
9	(9,0)

답이 될 수 있는 최댓값

아래 있는 최종 코드에서 x를 18자리 수 ($10^{18}$ 미만)까지만 탐색했다. 그 이상은 D가 주어진 값보다 무조건 커지기 때문이다.

소스 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

    ll d; cin >> d;
    ll ten[18]; ten[0]=1;
    for (int i = 1; i < 18; i++) ten[i] = ten[i-1] * 10;

    for (int i = 2; i <= 18; i++) {
        int n = (i/2);
        vector<ll> ten1;
        vector<ll> v1;
        ll t = d;
        for (int j = 0; j < n; j++) {
            ten1.push_back((ten[i-j-1]-ten[j]) / ten[j]);
        }
        for (int j = 0; j < n; j++) {
            int a;
            if (t >= 0) a = (10-t%10)%10;
            else a = (-10-t%10)%10;
            v1.push_back(a);
            t = (t - a * ten1[j])/10;
        }
        if (t == 0) {
            ll ans = 0;
            for (int j = 0; j < n; j++) {
                if (v1[j] == 0 && j == 0) ans += ten[i-1]+ten[0];
                if (v1[j] > 0) ans += (ten[i-1-j] * v1[j]);
                if (v1[j] < 0) ans -= (ten[j] * v1[j]);
            }
            cout << ans;
            return 0;
        }
    }
    cout << "-1";
}