알고리즘 - Python / 백준 - 1490번 : 자리수로 나누기

1490번: 자리수로 나누기 (acmicpc.net)

1490번: 자리수로 나누기

 

---

풀이

• 어떤 수 N이 주어졌을 떄 , N으로 시작하면서 N의 모든 자리수로 나누어 떨어지는 수를 찾는 문제이다.
• 어떤 수 N의 모든 자리수로 나누어 진다는 것은 , N의 모든 자리수의 최소공배수로 나누어 떨어진다는 것을 의미한다.
• 따라서 LCM을 활용해 최소공배수를 구하여 활용하면 연산시간을 조금이나마 더 줄일 수 있다.
• 각 자리수에 대해 전체 최소공배수를 구한 후 , N 뒤쪽에 자리수를 늘려가며 숫자를 붙여 최소공배수로 나누어 떨어질 때 break 하도록 두었다.
• PyPy3 채점환경에는 아직 math.lcm이 추가되지 않았으므로 Python3 채점환경을 통해 제출해야 한다.

 

import math
n = int(input())
leng = len(str(n))
s = []
for i in str(n):
    if i != "0":
        s.append(int(i))
s = list(set(s))
for i in range(1,len(s)):
    s[0] = math.lcm(s[0],s[i])
k = s[0]
if n%k == 0:
    print(n)
else:
    cnt = 1
    check = 0
    while True:
        for i in range(0,10**cnt):
            if int(str(n) + "0"*(cnt-len(str(i))) + str(i)) % k == 0:
                print(int(str(n) + "0"*(cnt-len(str(i))) + str(i)))
                check = 1
                break
        if check == 1:
            break
        cnt += 1

---