x+y=z 형식의 방정식을 나타내는 문자열 s가 있다고 가정합니다. 방정식이 참이 되도록 s에 더해야 하는 최소 자릿수를 찾아야 합니다.
따라서 입력이 s ='2+6=7'과 같으면 출력은 2가 됩니다.
"1"과 "2"를 삽입하여 방정식을 "21+6=27"로 바꿀 수 있습니다. 따라서 필요한 수정의 총 수는 2입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
"+" 문자를 기준으로 s를 부분으로 분할하고 왼쪽 부분을 A에, 오른쪽 부분을 나머지 부분에 넣습니다.
-
"=" 문자를 기준으로 나머지 부분을 분할하고 왼쪽 부분을 B에, 오른쪽 부분을 C에 넣습니다.
-
return dp(A - 1의 크기, B - 1의 크기, C - 1의 크기, 0)
-
dp() 함수를 정의합니다. 이것은 i, j, k, carry가 필요합니다.
-
i <=-1이고 j <=-1이고 k <=-1이면
-
캐리가 0과 같으면 0을 반환하고 그렇지 않으면 1
-
-
last1 :=(A[i]) i>=0이면 0
-
last2 :=(B[j]) j>=0이면 0
-
last3 :=(C[k]) k>=0이면 0이면 0
-
prefix1 :=(A[인덱스 0에서 i + 1까지]) i>=0 그렇지 않으면 0
-
prefix2 :=(B[인덱스 0에서 j + 1까지]) j>=0 그렇지 않으면 0
-
prefix3 :=(C[인덱스 0에서 k + 1까지]) k>=0 그렇지 않으면 0
-
i <=-1이고 j <=-1이면
-
rhs :=접두사3 - 캐리
-
rhs <=0이면
-
반환 |rhs|
-
-
i가 -1과 같거나 j가 -1과 같으면
-
문자열 rhs의 크기를 반환
-
-
그렇지 않으면
-
거짓을 반환
-
-
k <=-1이면
-
str(prefix1 + prefix2 + carry)의 반환 크기
-
-
ans :=무한대
-
carry2, lhs :=몫과 나머지를 10으로 나눈 나머지(carry + last1 + last2)를 반환
-
lhs가 last3과 같으면
-
ans :=dp(i - 1, j - 1, k - 1, carry2)
-
-
req :=last3 - 캐리 - last2
-
extra_zeros :=최대 0, -1 - i
-
carry2 :=req <0이면 1, 그렇지 않으면 0
-
ans :=ans의 최소값, 1 + extra_zeros + dp(최대값 -1, i, j - 1, k - 1, carry2)
-
req :=last3 - 캐리 - last1
-
extra_zeros :=최대 0, -1 - j
-
carry2 :=req <0이면 1, 그렇지 않으면 0
-
ans =(ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2))
의 최소값 -
carry2, lhs :=몫과 나머지를 10으로 나눈 나머지(last1 + last2 + carry)를 반환
-
ans :=ans의 최소값, 1 + dp(i - 1, j - 1, k, carry2)
-
반환
-
-
메인 메소드에서 return dp(크기 A – 1, 크기 B – 1, 크기 C – 1, 0)
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution:
def solve(self, s):
A, rest = s.split("+")
B, C = rest.split("=")
def dp(i, j, k, carry):
if i <= -1 and j <= -1 and k <= -1:
return 0 if carry == 0 else 1
last1 = int(A[i]) if i >= 0 else 0
last2 = int(B[j]) if j >= 0 else 0
last3 = int(C[k]) if k >= 0 else 0
prefix1 = int(A[: i + 1]) if i >= 0 else 0
prefix2 = int(B[: j + 1]) if j >= 0 else 0
prefix3 = int(C[: k + 1]) if k >= 0 else 0
if i <= -1 and j <= -1:
rhs = prefix3 - carry
if rhs <= 0:
return abs(rhs)
if i == -1 or j == -1:
return len(str(rhs))
else:
assert False
if k <= -1:
return len(str(prefix1 + prefix2 + carry))
ans = float("inf")
carry2, lhs = divmod(carry + last1 + last2, 10)
if lhs == last3:
ans = dp(i - 1, j - 1, k - 1, carry2)
req = last3 - carry - last2
extra_zeros = max(0, -1 - i)
carry2 = 1 if req < 0 else 0
ans = min(ans, 1 + extra_zeros + dp(max(-1, i), j - 1, k - 1, carry2))
req = last3 - carry - last1
extra_zeros = max(0, -1 - j)
carry2 = 1 if req < 0 else 0
ans = min(ans, 1 + extra_zeros + dp(i - 1, max(-1, j), k - 1, carry2))
carry2, lhs = divmod(last1 + last2 + carry, 10)
ans = min(ans, 1 + dp(i - 1, j - 1, k, carry2))
return ans
return dp(len(A) - 1, len(B) - 1, len(C) - 1, 0)
ob = Solution()
print (ob.solve('2+6=7')) 입력
'2+6=7'
출력
2