두 개의 숫자 A와 B가 주어졌을 때, A로 나누어 떨어지면서 각 자릿수의 합이 B와 같은 최소 양의 정수 M을 구해야 합니다. 만약 조건을 만족하는 수가 존재하지 않는다면 -1을 반환합니다.
예를 들어 입력이 A = 50, B = 2라고 가정해 보겠습니다. 이때 출력은 200이 됩니다. 200은 50으로 나누어 떨어지고, 자릿수의 합도 2 + 0 + 0 = 2로 B와 일치하기 때문입니다.
이 문제는 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 숫자를 왼쪽 자리부터 한 글자씩 붙여 가며 상태를 확장하고, 이미 방문한 상태는 다시 탐색하지 않음으로써 불필요한 중복 계산을 제거합니다.
알고리즘 단계
두 개의 정수 a(현재까지 수를 A로 나눈 나머지)와 b(자릿수 합), 그리고 하나의 문자열(현재까지 만든 수)을 함께 저장하는 요소(Element) 타입을 정의합니다.
que라는 새 리스트(큐)를 생성합니다.
(0, 0, 빈 문자열)로 초기화한 요소 elem을 만듭니다.
visited[0][0]을 1로 설정하여 시작 상태를 방문 처리합니다.
elem을 que의 끝에 삽입합니다.
que의 크기가 0보다 큰 동안 아래 과정을 반복합니다.
que에서 첫 번째 요소를 꺼내 temp_elem에 저장합니다.
temp_elem.a가 0이고 temp_elem.b가 b와 같다면, temp_elem.string을 정수로 변환하여 반환합니다. (a가 0이라는 것은 현재까지 만든 수가 A로 나누어 떨어진다는 의미입니다.)
i를 0부터 9까지 반복하며 다음을 수행합니다.
x := (temp_elem.a * 10 + i) mod a
y := temp_elem.b + i
y <= b이고 visited[x][y]가 False라면, visited[x][y]를 1로 표시하고 새로운 요소(x, y, 기존 문자열에 i를 이어 붙인 값)를 que에 삽입합니다.
반복이 종료될 때까지 답을 찾지 못했다면 -1을 반환합니다.
구현 예제
아래 파이썬 코드를 통해 동작 방식을 더 잘 이해할 수 있습니다.
visited = [[0 for x in range(501)] for y in range(5001)]
class Element:
def __init__(self, a, b, string):
self.a = a
self.b = b
self.string = string
def get_number(a, b):
que = []
elem = Element(0, 0, "")
visited[0][0] = 1
que.append(elem)
while len(que) > 0:
temp_elem = que.pop(0)
if temp_elem.a == 0 and temp_elem.b == b:
return int(temp_elem.string)
for i in range(0, 10):
x = (temp_elem.a * 10 + i) % a
y = temp_elem.b + i
if y <= b and visited[x][y] == False:
visited[x][y] = 1
que.append(Element(x, y, temp_elem.string + str(i)))
return -1
a, b = 50, 2
print(get_number(a, b))입력
50, 2
출력
200
위 코드는 가능한 모든 숫자 후보를 자릿수 합과 나머지 정보로 압축하여 관리하기 때문에, 무작정 큰 수를 하나씩 검사하는 방법보다 훨씬 빠르게 정답을 찾을 수 있습니다.