백준 1078 - 뒤집음

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

1078번: 뒤집음

정말 너무 어려운 문제였다. 애초에 이건 알고리즘 문제보다 수학 문제에 가까웠다.

정말 어렵지만, 설명할 수 있는 만큼 최대한 자세하게 설명했으니 도움이 되길 바란다.

공식분석하기

X에 대한 공식

$$ X = a_0 * 10^{L-1} + a_1 * 10^{L-2} +... + a_{L-1} * {10^0} $$

이 때 자릿수는 0부터 센다.

먼저 X는 자릿수의 수 * 10의 (총자릿수 - 1 - 자릿수) 승의 합이다.
1234라는 4자리 숫자를 예로 들자면, 다음과 같다.
$$ 1234 = 1 * 10^{4 - 1 - 0} + 2 * 10^{4 - 1 - 1} + 3 * 10^{4 -1 -2} + 4 * 10^{4 -1-3} $$

 

X를 뒤집은 수 X'에 대한 공식

$$X' = a_0 * 10^{0} + a_1 * 10^{1} +... + a_{L-1} * 10^{L-1}$$

그리고 X를 뒤집은 수 X'에 대해서는 위와 같은 식이 나온다.

1234를 뒤집어보면 다음과 같다.

$$ 1234의 뒤집은 수 = 1 * 10^{0} + 2 * 10^{1} + 3 * 10^{2} + 4 * 10^{3} = 4321 $$

 

X와 X'를 빼자

$$ X-X' = a_0 * (10^{L-1}-10^0) + a_1 * (10^{L-2}-10^1) +...+ a_{L-2} * ({10^1}-10^{L-2})+ a_{L-1} * ({10^0}-10^{L-1}) $$

$$ = a_0 * (10^{L-1}-10^0) + a_1 * (10^{L-2}-10^1) +...- a_{L-2} * (10^{L-2}-{10^1})- a_{L-1} * (10^{L-1}-{10^0}) $$

$$ = (a_0 - a_{L-1}) * (10^{L-1}-10^0) + (a_1 -a_{L-2}) * (10^{L-2}-10^1)+... $$

이제 위에서 살펴본 X와 X'를 빼면 위와 같은 식이 나온다.
주의할 점은 두 번째 수식에서 후반 수식(+... 이후)의 부호가 바뀌었고,
세번째 수식에서 이 식들을 묶어줬다는 것이다.

 

후, 이제 검증으로 X=1234를 이 식에 대입해보면 다음과 같다.

$$X \text{가 1234인 경우 }X-X'= (1-4)(10^3-10^0)+(2-3)(10^2-10^1) $$

$$ =-3*999+(-1)*90=-3087 $$

그리고 실제로 1234-4321=-3087이다.

 

공식 끝! 체크포인트

후... 여기까지 봤다면 정말 수고많았다. 머리가 아마 많이 아팠을 수도 있고,
본인이 원래 수학 씹고수라면 쉬웠을 수도 있다.
나는 미적분도 뭔지 모르는 머저리라 다른 블로그들 설명 읽으면서
여기까지 계산하는데 머리가 깨질 뻔했다.
(설명이 불친절해서 혼자 열심히 정리한 거임, 복붙한 거 아님, 참고한 블로그는 아래 남기겠다!)

그리고 여기서 알아야 하는 부분이 있다.

 

체크1: D=9의 배수가 아니라면 X는 존재하지 않는다.

$$ 10^m-10^n mod 9 = 0 \text{ 조건:} m!=n $$

위 식이 성립한다. 생각해보면 10의 제곱수들은 맨 앞자리가 1이고 나머지는 다 0이다.
따라서 10의 제곱수들끼리의 자강두천(;;뺄셈)이 일어나면,
그 결과값은 9와 0으로만 구성된다.
즉, 10의 제곱수들의 차는 모두 9의 배수이다.
그리고 X-X’의 식을 보면 9의 배수인 10의 제곱수들의 차와 자릿수의 수를

곱한 후 더하기때문에 X-X’의 차인 D는 반드시 9의 배수여야 한다.

 

체크2: 두 자릿수의 차를 구했다면, 두 자릿수의 수가 결정된다.

두 자릿수의 차에 관해 다음 식이 성립한다.

$$-9 <= a_n-a_m <=9$$

위 식은 $a_n$과 $a_m$에 올 수 있는 값이 0~9이기때문에 당연한 것이다.
또한 이 때 이 차를 알아낸다면, X의 n번째 자리와 m번째 자리의 수를 특정할 수 있다.

예를 들어 D가 999라고 해보자.

$$(a_0-a_3)*(10^3-10^0)+(a_1-a_2)*(10^2-10^1) = 999$$

$$(a_0-a_3)*999+(a_1-a_2)*90=999$$

 

위 식이 성립하기 위해서 각 자릿수의 수는 다음과 같아야 한다.

$$a_0-a_3=1, a_1-a_2=0$$
이를 최솟값으로 성립시키려면 다음과 같다.

$$a_0=1, a_3=0, a_1=0,a_2=0$$

즉, 1000이 X가 될 것이다.

하지만 이를 최댓값으로 성립시키려면 각 자릿수의 수는 다음과 같다.

$$a_0=9,a_3=8,a_1=9,a_2=9$$
즉, 9998이 X가 된다.

 

이에 따라 최솟값으로 성립시키기 위한 규칙이 생기는데, 앞자리 숫자에 가장 작은 숫자를 넣어야 한다는 것이다.
이에 따라 n < m일 경우 다음 규칙이 성립한다. 

$$a_n - a_m$$	$$(a_n, a_m)$$
-9	0, 9
-8	0, 8
-7	0, 7
...	...
0	(0, 0), 맨 앞자리에서만 (1,1)
...	...
7	7,0
8	8,0
9	9,0

단, 자릿수의 차가 0일 경우 예외가 있는데, 맨 앞자리와 맨 뒷자리의 차가 0이어야 하는 경우
0을 대입하면 자릿수가 줄어들어 자릿수의 수에 곱해지는 계수(10의 배수의 차)가 틀려진다.
따라서 맨 앞자리의 경우 1을 대입해야 한다.

 

체크3: 자릿수의 차를 구할 때 끝을 0으로 맞추자!

$n>m$인 경우 다음 규칙이 성립한다.

$m=0일 때,10^n-10^0$은 9로만 이루어진다.

$m=1일 때,10^n-10^1$은 9와 0 하나로 이루어진다.

$m=2일 때,10^n-10^2$은 9와 0 둘로 이루어진다.

즉 $10^n-10^m$은 9와 0 $m$개로 이루어진다.
생각해보면 $10^1$은 0이 하나고, $10^2=100$이니 0이 둘이다.
그러니 큰 10의 제곱수에서 작은 10의 제곱수를 빼면,
작은 10의 제곱수의 0의 개수만큼만큼 0이 확보된다.

즉, X와 X'를 뺀 $ = (a_0 - a_{L-1}) * (10^{L-1}-10^0) + (a_1 -a_{L-2}) * (10^{L-2}-10^1)+... $ 이 식에서,
계수(10의 제곱수의 차)는 위 조건이 만족한다면 0이 하나씩 늘어나게 된다.

이에 따라 우리는 자릿수의 차를 구할 때 0을 하나씩 확보해줘야 한다.

 

909를 D로 가지는 X를 구한다고 하자.

체크2의 식을 그대로 적용한다. 다음과 같다.

$$(a_0-a_3)*999+(a_1-a_2)*90=909$$

이 때 먼저 $a_0-a_3$를 구해야 한다.
다음 수는 0이 하나 늘어나있을 것이기때문에 끝을 0으로 맞추기 위해 $a_0-a_3=1$로 맞춰야 한다.

그러면 $999 + (a_1-a_2)*90=909, (a_1-a_2)*90 = -90$이 성립한다.
따라서 $(a_1-a_2)=-1$이 되고, $a_0=1,a_3=0,a_1=0,a_2=1$이 된다.
즉, 답은 1010이 된다.
9*0에서 9*9까지 보면 (0,9,8,7,6,5,4,3,2,1)로 0~9까지 겹치지 않고 존재하는 것을 알 수 있다.
즉, 우리는 목표수와 빼서 끝자리가 0으로 맞춰지는 수 하나만 찾으면 된다.
(이 부분이 이해가 잘 안 될 수도 있는데, 코드를 보면 어느 정도 이해가 될 거다)

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Integer.parseInt;

// 백준 1078 - 뒤집음
public class Main {

    static long N, tens[] = new long[13];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = parseInt(br.readLine());

        if (N % 9 != 0) {
            System.out.println(-1);
            return;
        }

        //tens 배열에 10의 제곱수들을 저장
        tens[0] = 1;
        for (int i = 1; i < 13; i++) {
            tens[i] = tens[i - 1] * 10;
        }

        //i= 총자릿수이다.
        for (int i = 2; i < 13; i++) {
            //10의 제곱수의 차의 개수 > 간단히 weights 배열의 길이
            //ex) 10000의 경우 > 9999, 990 2개이다.
            int n = i / 2;

            long[] weights = new long[n];
            int[] difList = new int[n];

            /*10의 제곱수의 차 계산
            이 때 중요한 점은 제곱수의 차를 계산하고 tens[j]로 나눈다는 점이다.
            tens[j]의 0의 개수만큼 계산 결과는 0을 가진다. ex) 100000 - 100 = 99900 > 10의 2승이고 0을 2개 가진다
            이 0을 제거해서 결과에 9만 남게 하는 것이다.
            이렇게 하지 않으면, dif(각 자릿수의 차)를 구하는 과정에서
            다음 제곱수의 차에 0이 몇 개 있는지를 생각해서 생각해서 0의 개수를 맞춰줘야 한다.
            이는 힘들기때문에 weights에서 깔끔하게 0을 없애고, dif를 계산할 때마다 0을 하나씩 만든 후 제거한다.
             */
            for (int j = 0; j < n; j++) {
                weights[j] = (tens[i - 1 - j] - tens[j]) / tens[j];
            }

            long t = N;
            for (int j = 0; j < n; j++) {
                //t의 1의 자리 수를 구한다
                int dif = (int) (t % 10);

                //t의 1의 자리를 10에서 뺀다. > 해당 수를 9와 곱하면 끝자리를 0으로 맞출 수 있다.
                //그리고 현재 wegihts에 저장된 계수들은 모두 9로 구성된다.
                //ex) t=503일 때, 10 - 3 = 7이고, 9 * 7 = 63 > 503 - 63 = 440이 된다.
                if (t > 0) {
                    dif = 10 - dif;
                } else if (t < 0) {
                    dif = -10 - dif;
                }

                // |dif|가 10인 경우, dif를 0으로 만들어준다
                dif %= 10;
                //두 자릿수의 차가 계산되었다.
                difList[j] = dif;

                /*계수(0을 제거한 10의 제곱수의 차) * 두 자릿수의 차를 곱해서, t에서 빼준다.
                이렇게 하면 끝에 0이 하나 남게 된다. 왜냐하면 weights는 모두 9로 구성되어있고, dif를 고의적으로 9와 곱해서 0이 나오는 수로 맞췄기때문이다.
                그 0을 제거하기 위해서 10으로 나눠준다.
                어차피 10의 제곱수의 차에서 0은 매번 하나씩 늘어나기때문에, 매번 하나의 0만 만들어주고, 그걸 10으로 나눠주면 문제가 없다.
                이를 위해서 weights에서 0을 제거한 것이다.
                 */
                t = (t - weights[j] * dif) / 10;
            }

            if (t == 0) {
                long ans = 0;
                for (int j = 0; j < n; j++) {
                    /*참고: 공식에서 봤듯이 10^(총자릿수 - 1 - 자릿수)승이 각 자릿수의 계수가 된다.
                    또한 각 자릿수에 대칭되는 자릿수의 계수는 10^자릿수 승이 된다.
                     */

                    //두 자릿수의 차가 0이고 맨 앞자리인 경우, 맨 앞과 맨 끝을 1과 1로 맞춰줘야 한다.
                    //이를 위해 10^(총자릿수 - 1 - 자릿수{=0}) + 1을 ans에 해준다.
                    if (j == 0 && difList[j] == 0) {
                        ans += tens[i - 1] + 1;
                    }
                    /*참고로 j=0일 때, 반드시 두 자릿수의 차 >= 0이다.
                    따라서 j=0일 때 이 두 if문 중 하나에 걸린다.
                    두 자릿수의 차가 0보다 큰 경우 (두 자릿수의 차)가 j번째에 들어가면 된다.
                    이를 위해 (자릿수의 게수) * (두 자릿수의 차)를 수행한다.
                    */
                    else if (difList[j] > 0) {
                        ans += tens[i - 1 - j] * difList[j];
                    }
                    /*두 자릿수의 차가 0보다 작은 경우 (두 자릿수의 차)가 뒤에서 j번째에 들어가야 한다.
                    이 자릿수에 대칭되는 수의 계수는 10^자릿수 승이 된다.
                    이를 위해 (자릿수의 계수) * (두 자릿수의 차)를 수행하고, ans에서 뺀다.
                    빼는 이유는 결과값이 음수인데, 원하는 동작은 그만큼 숫자를 올리는 것이기때문에 빼야 한다.
                     */
                    else if (difList[j] < 0) {
                        ans -= tens[j] * difList[j];
                    }
                }

                System.out.println(ans);
                return;
            }
        }
        System.out.println("-1");
    }
}

 

참고: https://ggyuchive.tistory.com/14