백준 16233, 수학 문제

개요

문제 링크
골드 1, 정수론
X-(X의 자리수합) = N이 되는 최소 X구하기

---

접근

1. 분류가 수학으로 되어있는데 정수론에 가까운 것 같아 정수론으로 분류했다. 우선 기본적인 생각을 한 뒤 노가다를 돌려보자.
2. 기본적인 생각이란? X는 N과 자리수 차이가 많이 나지 않는다. 왜냐? N의 자리수 합의 최댓값은 9가 9개 있는 999999999의 81이다. 최대로 81 쯤까지 더할 수 있는데, 자리수가 2이상 차이나면 N-X 가 81을 넘어버린다. 그러니 N*10까지 검사해보자.

int sum(int x)
    while (x/=10)
        sum += x%10
    return sum

for (x = n~n*10)
    if (x-sum(x) == n)
        return x
return -1

이렇게 1000이나 10000까지 돌려보자. 그 이상은 TLE가 날 것이다. 그런데 규칙성을 잘 보면 9의배수가 아닌 수는 안되는 것을 확인할 수 있다. 왜냐?

3. 어떤 10진수는 아래와 같이 나타낼 수 있다.

X = a[n]*(10^n) + a[n-1]*(10^n-1) + ... + a[0]*(10^0)

그럼 여기서 각 자리수를 빼준다면?

sum(X) = a[n] + a[n-1] + ... + a[0]
X-sum(X) = 999...999 * a[n] + 999...99 * a[n-1] + ... + 99*a[2] + 9*a[1]

a[n]이 [0,9]의 정수이므로 모든 수가 9의 배수가 된다. X-sum(X)의 표현을 편의상 9e진법이라고 해보자.

4. 그런데 9의 배수중에서 90이 안된다. 왜 90은 안될까? 9e진법으로 나타낼 수 없기 때문이다.

90 = 99*0 + 9*10
a[1] = 0, a[0] = 10

a[0]이 9보다 크기 때문에 9e진법 표현이 불가능하다. 그래서 우리는 9의 배수 중, 9e진법으로 표현가능한 수를 찾아주면 된다.

5. 그런 다음 N에서 N*10까지 돌려주면서 X를 찾아주면 될까? T가 많아서 TLE가 난다. 그럼 O(n)보다 작은 시간에 찾아줘야 하는데, 어떻게 할까?

X = a[n]*(10^n) + a[n-1]*(10^n-1) + ... + a[0]*(10^0)

X는 위와 같이 10진법 표현이 가능했다. 그리고 우리는 9e진법의 유효성 여부를 확인하면서 a[0]부터 a[n]을 구할 수 있다. 9e진법의 유효성 여부를 확인하는 과정에서 구한 각 자리수를 이용해 바로 10진수로 복원을 해주면 된다.

---

Pseudo code

9e (N) {
    int R = 999999999 // 9가 9개
    int X = 0
    while (R)
        Ai = N/R
        if (9 < Ai) return -1

        N %= R
        R /= 10 // 9를 한개 줄여줌
        X += Ai, X *= 10
    return X
}

if (n%9) return -1
return 9e(n)

---

Source code

#include <iostream>
using namespace std;

int mod(int n) {
    int r = 999999999;
    int x = 0;
    while (r) {
        if (9<(n/r))
            return -1;
        x = (x+n/r)*10;
        n %= r;
        r /= 10;
    }
    return x;
}

int test() {
    int n;
    scanf("%d",&n);
    if (n%9) return -1;
    return mod(n);
}

int main() {
    int t;
    cin >> t;
    while(t--)
        printf("%d ",test());
}