백준 1490(자리수로 나누기) - 해결

자리수로 나누기

 

문제

어떤 수 N이 주어졌을 때, N으로 시작하면서, N의 0이 아닌 모든 자리수로 나누어지는 떨어지는 수 중 가장 작은 수를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 어떤 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 답을 출력한다.

---

브루트포스 문제라서 하나하나 확인하는 방법을 생각하였다.

처음 N 으로 가능한지 확인을 하고 불가능하다면 뒤에 숫자를 증가하면서 확인하는 방법을 사용하였다.

idx로 0~9, 00~99, 000~999 이렇게 빈칸은 0으로 채우면서 확인하는 방식으로 풀었다.

import sys
input = sys.stdin.readline

input_num = input().strip()
# 포함되어 있는 숫자 종류
num_set = set(map(int,input_num))
# 0은 제거
if 0 in num_set:
    num_set.remove(0)

# 자릿수를 늘리기 위해서
idx = 1
# 종료하기 위해서
flag = False

# 그 자체로 가능할 때
for num in num_set:
    now_num = int(input_num)
    if now_num % num:
        break
else:
    flag = True

# 가능하지 않으면 숫자를 추가하기
if not flag:
    while 1:
        # 10**idx 만큼 뒤에 붙여서
        for i in range(10**idx):
            # 숫자 만들기
            now_num = int(input_num + str(i).zfill(idx))
            
            # 확인하기
            for num in num_set:
                if now_num % num:
                    break
            else:
                flag = True
                break
        # 인덱스 증가와 확인하기   
        idx += 1
        if flag:
            break

print(now_num)