백준 16680 안수빈수 문제 풀이
백준 온라인 저지, 16680번: 안수빈수
도입
수빈수는 자릿수의 합이 짝수인 정수, 안수빈수는 자릿수의 합이 홀수인 정수이다. 문제에서 예시로 제시한 $1093$은 $1 + 0 + 9 + 3 = 13$, 홀수이므로 안수빈수라고 파악할 수 있다.
문제의 요구 사항은 어떤 $N$에 대해 $N$의 배수에 안수빈수가 존재한다면 안수빈수를, 그렇지 않으면 $-1$을 출력하는 것이다.
풀어보기
자릿수의 합 구하기
어떤 수의 자릿수의 합은 그 수를 9로 나눈 나머지와 같다.
$X = d_n * 10^n + d_{n-1} * 10^{n-1} + … + d_1 * 10^1 + d_0 * 10^0$
$S(X) = d_n + d_{n-1} + … + d_1 + d_0$$10 \equiv 1$ $\pmod 9$
$10^k \equiv 1^k ≡ 1$ $\pmod 9$$X = d_n * 10^n + d_{n-1} * 10^{n-1} + … + d_1 * 10^1 + d_0 * 10^0$
$X \equiv d_n * 1 + d_{n-1} * 1 + … + d_1 * 1 + d_0 * 1 $ $\pmod 9$
$X \equiv d_n + d_{n-1} + … + d_1 + d_0$ $\pmod 9$$S(X) \equiv X$ $\pmod 9$
N의 배수 중 안수빈수 찾기
문제 요구사항을 만족하기 위해서는 주어진 $N$에 대하여, $N$의 배수 중 안수빈수가 존재하는지 확인해야 한다.
안수빈수 $N \times M$의 형태에서 $M$을 적절히 선택하면 자릿수의 합을 쉽게 예측할 수 있다. $M$을 $10^{k^\prime} - 1$으로 생성할 수 있는 수, 다시 말해 $99…9$ 형태의 수로 선택하면, $M$은 항상 9의 배수이다.
- $M = 10^{k^\prime} - 1$ 라면 $N \times M = N \times (10^{k^\prime} - 1)$
- $N \times (10^{k^\prime} - 1) = N \times 10^{k^\prime} - N$
- $N \times 10^{k^\prime} - N = (N-1) \times 10^{k^\prime} + (10^{k^\prime} - N)$
$N=123, k^\prime=5$ 라면 도출한 식의 각 항을 분리하여 다음과 같이 계산할 수 있다:
- A: $(N-1) \times 10^{k^\prime} = 122 \times 10^5 = 12,200,000$
- B: $(10^{k^\prime} - N) = 10^5 - 123 = 100000 - 123 = 99,877$
$N \times (10^{k^\prime} - 1) = 12,200,000 + 99,877 = 12,299,877$
A값은 B값 후미에 0으로 채워진 부분을 넘지 않는다. 다시 말해 결과값의 자리수의 합은 <자릿수의 합 구하기> 공식에 따라 $S(\text{A}) + S(\text{B})$로 확인할 수 있다. $S(\text{A}) + S(\text{B}) = S(N-1) + S(10^{k^\prime} - N)$ 이므로, 자리수의 합은 $9k^\prime$와 같다.
이 문제에서 $N$의 최대값은 $10^8$이고, $10^{18}$ 이하의 아무 안수빈수를 출력하면 되므로, $k\prime$을 9로 설정할 수 있다. 이와 같이 설정하면, $N \times (10^9 - 1)$의 자릿수의 합은 항상 $9 \times 9 = 81$이다.
마무리
이 문제의 입력 조건을 고려하면, $N$의 배수 중에서 자릿수의 합이 81인 안수빈수를 항상 찾을 수 있다.
1
2
3
4
>>> set([sum(
... map(lambda x: int(x), str(i * (int(1e9) - 1)))
... ) for i in range(1, int(1e9))])
{81}