n으로 나누어 떨어지면서 자릿수의 합도 n으로 나누어 떨어지는 정수

30599번: Divisibility Trick (acmicpc.net)

 

3의 배수 판정법은 어떤 정수의 자릿수 합이 3으로 나누어 떨어지면, 3의 배수이다.

 

9의 배수도 마찬가지다.

 

어떤 정수 n의 자릿수의 합이 d로 나누어 떨어지면서 n도 d로 나누어 떨어지는 정수 n을 아무거나 하나 찾으면 된다

 

생각했던 방법은 각 자릿수는 0~9까지니까 자릿수 합이 d로 나누어 떨어지게 되는 가장 작은 수는

 

'1'을 d개만큼 이어 붙이는 것이라고 생각했다. 

 

x = 111111111111111111111111111.....1111111

 

이러면 자릿수 합이 d니까 d로 나누어 떨어진다.

 

이 x를 d로 나누었을 때 x = d*p + r이 될 것인데 d(p+1)부터 시작해서 d(p+2), d(p+3), ....을 모두 조사해보는 것이다.

 

d*i꼴이니까 이 정수는 d로 나누어 떨어지는 것은 확실하다.

 

이들 중 자릿수 합이 d의 배수인것만 찾으면 바로 print

 

d = int(input())

i = int('1'*d)//d+1

while 1:

    s = str(d*i)

    v = sum(map(int,s))

    if v % d == 0:
        
        print(s)
        break

    i += 1

 

 

 pypy로 2.6초로 겨우 뚫리긴 하더라

 

근데 더 확실하고 놀라운 풀이가 있는데

 

d를 d번 이어붙인다.

 

dddddddddd...dd

 

얘는 d의 배수인데, 어떤 정수 n1,n2,n3,..에 대하여

 

$d*10^{n1} + d*10^{n2} + d*10^{n3}... + d$로 나타낼 수 있기 때문이다.

 

자릿수 합은 d*d이므로 d로 나누어 떨어진다.

 

#정수 n은 d의 배수이면서 자릿수 합도 d의 배수이다.
#그러한 정수 n은 d를 d번 이어 붙인 수가 해당될 수 있다.
d = input()

answer = []

for _ in range(int(d)):
    
    answer.append(d)

print(''.join(answer))