[BOJ Solution] BOJ1078 - 뒤집음

https://www.acmicpc.net/problem/1078

1078번: 뒤집음

자릿수에 관한 관찰이 필요한 문제이다. 따라서 0-based index로 $i$번째 자릿수를 $a_i$로 정의하는 것이 문제 풀이에 도움이 될 것이다.

이때 문제의 정답이 되는 최소의 자연수를 $X$, $X$를 뒤집은 수를 $\bar{X}$, $X$의 길이를 $L$이라 하자. 정의에 의해 다음의 세 가지 식이 성립한다.

1. $\displaystyle X=\sum_{i=0}^{L-1}a_i\times10^{i}$

2. $\displaystyle \bar{X}=\sum_{i=0}^{L-1}a_i\times10^{L-i}$

3.  $X-\bar{X}=D$

1,2번 식을 3번 식에 대입하여 정리하면 다음과 같은 식을 얻을 수 있다.

$$\sum_{i=0}^{\lfloor L/2\rfloor}(a_{L-i-1}-a_{i})\times10^{i}\times(10^{L-2i}-1) = D$$

여기서 임의의 음이 아닌 정수 $k$에 대해 $10^k \mod 9 = 1$이라는 사실을 떠올려보자. 양변을 9로 나눈 나머지를 취해보면, 좌변은 나머지가 0이므로 $D$ 역시 9로 나눈 나머지가 0이 되어야 한다. 그렇지 않은 경우 우측과 같은 표현법이 존재하지 않아 $X$와 $\bar{X}$가 존재하지 않음을 확인할 수 있다.

다만, $D$가 9의 배수라고 항상 이러한 표현법이 존재한다고 이야기할 수는 없다. 실제로 $D$로부터 $X$를 찾는 과정에서 그 조건을 더 자세히 확인해보자.

우리는 $D$가 9의 배수임을 확인하였으므로 자연수 $D^\prime=D/9$를 얻을 수 있다. $-9\le a_{L-i-1}-a_{i}\le9$, $10^{L-2i}-1=1111....111$이므로 $D^\prime \mod 10$은 $a_{L-1}-a{0}$와 같다. 이러한 성질을 이용하여 $i$를 점점 증가시키며 $a_{L-i-1}-a_i$를 구할 수 있다. 이 값을 구했을 때 부호에 따라 적절히 처리해주면 최소의 $X$를 구할 수 있다. 모든 $i$에 대해 시행한 후에 $D$가 0이 아니라면 $X$가 존재하지 않는다는 것을 알 수 있다.

위의 모든 풀이가 정답의 길이 $L$을 알 때 사용할 수 있는 풀이이나 $L$의 범위는 굉장히 작다는 점이다. 따라서 작은 $L$부터 증가하는 순서대로 시도하여 답을 구할 수 있다.

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

ll ipow(ll a,int n){
    if(n==0)return 1;
    if(n==1)return a;
    if(n==2)return a*a;
    ll res = ipow(a*a,n/2);
    if(n%2)res *= a;
    return res;
}

ll f(ll D,int l){
    ll res = 0;
    ll Dp=D;
    for(int i=0;2*i<l;i++){
        if(D%10>0||(D%10==0&&i!=0))res += D%10*ipow(10,l-i);
        if(D%10==0&&i==0)res += ipow(10,l-i)+(l-i!=i)*ipow(10,i);
        if(D%10<0)res -= D%10*ipow(10,i);
        D-=D%10*(ipow(10,l-2*i)-1)/9;
        D/=10;
    }
    if(D)return -1;
    else return res;
}

int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    ll D;
    cin>>D;
    if(D%9){
        cout<<"-1";
        return 0;
    }
    D/=9;
    for(int i=1;i<=17;i++){
        ll r = f(D,i);
        if(r!=-1){
            cout<<r;
            return 0;
        }
    }
    cout<<"-1";
    return 0;
}