목표 숫자(target)가 주어졌을 때, 두 개의 정수 A와 B를 원하는 만큼 여러 번 더해서 그 값을 만들 수 있는지 확인하는 문제입니다.
예를 들어 Target = 26, A = 5, B = 7이 입력으로 주어진다면, 26은 7 + 7 + 7 + 5처럼 A와 B를 반복해서 더해 만들 수 있으므로 결과는 True가 됩니다.
해결 접근 방법
이 문제는 깊이 우선 탐색(DFS)과 메모이제이션을 활용하면 효율적으로 해결할 수 있습니다. 0부터 시작해 A 또는 B를 계속 더해가며 도달 가능한 모든 숫자를 배열에 표시하고, 최종적으로 target 값에 도달했는지만 확인하면 됩니다.
구체적인 절차는 다음과 같습니다.
- util() 함수를 정의합니다. 이 함수는 x, a, b, is_ok, target을 매개변수로 받습니다.
- x가 target보다 크면 더 이상 탐색할 필요가 없으므로 즉시 반환합니다.
- is_ok[x]가 이미 True라면 같은 숫자를 중복 탐색하지 않도록 바로 반환합니다.
- is_ok[x]를 True로 표시합니다.
- util(x + a, a, b, is_ok, target)과 util(x + b, a, b, is_ok, target)을 재귀 호출하여 다음 단계를 탐색합니다.
메인 로직
- 크기가 (target + 1)인 불리언 배열 is_ok를 생성하고 False로 초기화합니다.
- util(0, a, b, is_ok, target)을 호출해 0부터 탐색을 시작합니다.
- is_ok[target]의 값을 반환합니다. True라면 target을 만들 수 있다는 의미입니다.
예제 코드
아래 구현 예제를 통해 동작 방식을 더 쉽게 이해할 수 있습니다.
def util(x, a, b, is_ok, target):
if x > target:
return
if is_ok[x]:
return
is_ok[x] = True
util(x + a, a, b, is_ok, target)
util(x + b, a, b, is_ok, target)
def solve(target, a, b):
is_ok = [False] * (target + 1)
util(0, a, b, is_ok, target)
return is_ok[target]
target = 26
A = 5
B = 7
print(solve(target, A, B))입력
26, 5, 7
출력
True
이 알고리즘은 각 숫자를 한 번씩만 방문하므로 시간 복잡도는 O(target)이며, target 값이 클 때도 안정적으로 동작합니다.