프로그래밍 문제에서 자주 만나는 상황 중 하나는 다음과 같습니다. 하나의 숫자 n과 두 개의 숫자 a, b가 주어졌을 때, a와 b의 자릿수만으로 구성된 어떤 수가 n을 나누어 떨어지게 할 수 있는지 확인해야 하는 경우입니다.
예를 들어 입력이 n = 115, a = 3, b = 2라고 가정해 보겠습니다. 이때 2와 3으로 구성된 수 23이 115를 정확히 나누므로(115 ÷ 23 = 5) 결과는 True가 됩니다.
해결 접근 방식
이 문제는 재귀(Recursion)를 활용하면 간단하게 해결할 수 있습니다. 핵심 아이디어는 a와 b로 만들 수 있는 모든 수를 차례대로 생성하면서, 각 단계마다 해당 수가 n을 나누어 떨어지게 하는지 확인하는 것입니다.
알고리즘 단계
util()함수를 정의합니다. 이 함수는 temp, a, b, n 네 개의 매개변수를 받습니다.- temp가 n보다 크면 더 이상 유효한 후보가 아니므로 False를 반환합니다.
- n이 temp로 나누어 떨어지면(n % temp == 0) 조건을 만족하므로 True를 반환합니다.
- 그렇지 않으면 temp 뒤에 a 또는 b를 이어 붙인 새로운 수(temp * 10 + a, temp * 10 + b)에 대해 재귀적으로 탐색을 계속합니다. 두 호출 중 하나라도 True를 반환하면 True를, 모두 False이면 False를 반환합니다.
- 메인 함수에서는 시작점으로 a와 b 각각에 대해 util()을 호출하고, 하나라도 True이면 최종 결과는 True입니다.
구현 예제
다음 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
def util(temp, a, b, n):
if temp > n:
return False
if n % temp == 0:
return True
return util(temp * 10 + a, a, b, n) or util(temp * 10 + b, a, b, n)
def solve(n, a, b):
return util(a, a, b, n) or util(b, a, b, n)
n = 115
a = 3
b = 2
print(solve(n, a, b))입력
115, 2, 3
출력
True
동작 원리 살펴보기
위 예제에서 알고리즘은 다음과 같은 순서로 동작합니다.
- 먼저 util(3, ...)을 호출합니다. 3은 115를 나누지 못하므로 탐색을 계속 진행합니다.
- 3 뒤에 3 또는 2를 붙여 33과 32를 검사하지만, 둘 다 115를 나누지 못합니다.
- 다음으로 util(2, ...)를 호출합니다. 2 역시 115를 나누지 못하므로 23과 22를 검사합니다.
- 23은 115를 정확히 나누므로(115 ÷ 23 = 5) True가 반환되고, 최종 결과도 True가 됩니다.
이 방법의 시간 복잡도는 탐색 깊이 d에 대해 대략 O(2^d) 형태입니다. 각 단계마다 두 가지 선택지(a 또는 b 추가)가 생기기 때문입니다. 다만 temp가 n을 초과하는 즉시 탐색을 중단하므로, 실제 탐색 공간은 n의 자릿수에 따라 자연스럽게 제한됩니다.