숫자 목표가 있다고 가정합니다. A와 B라는 두 개의 숫자가 더 있습니다. A와 B를 원하는 만큼 추가하여 목표물을 얻을 수 있는지 확인해야 합니다.
따라서 입력이 Target =26 A =5 B =7과 같으면 (7 + 7 + 7 + 5)와 같이 A와 B를 추가하여 26을 얻을 수 있으므로 출력은 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- util() 함수를 정의합니다. x, b, is_ok, target 이 필요합니다.
- 만약 x>타겟이면
- 반환
- is_ok[x]가 True이면
- 반환
- is_ok[x] :=참
- 유틸(x + a, b, is_ok, 대상)
- util(x + b,, b, is_ok, 대상)
- 메인 방법에서 다음을 수행하십시오 -
- is_ok :=크기의 배열(대상 + 1)이고 False로 채우기
- 유틸(0, b, is_ok, 대상)
- is_ok[대상]을 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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