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

 

1078번: 뒤집음

어떤 수를 뒤집는다는 것은 오른쪽부터 다시 쓰는것이다. 예를 들어, 1234를 뒤집으면 4321이 되고, 100을 뒤집으면 1이 된다. (앞에 0은 무시) 어떤 수 D가 주어질 때, x – (x를 뒤집은 수)가 D가 되는

www.acmicpc.net

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

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

1. X=i=0L1ai×10i

2. X¯=i=0L1ai×10Li

3.  XX¯=D

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

i=0L/2(aLi1ai)×10i×(10L2i1)=D

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

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

우리는 D가 9의 배수임을 확인하였으므로 자연수 D=D/9를 얻을 수 있다. 9aLi1ai9, 10L2i1=1111....111이므로 Dmod10aL1a0와 같다. 이러한 성질을 이용하여 i를 점점 증가시키며 aLi1ai를 구할 수 있다. 이 값을 구했을 때 부호에 따라 적절히 처리해주면 최소의 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;
}

+ Recent posts