이 문제에서는 큰 정수 값(최대 10 5 숫자). 우리의 임무는 최대 부품을 3으로 나눌 수 있도록 필요한 총 절단 수를 인쇄하는 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력 − 9216
출력 - 3
설명 - 숫자는 9|21|6으로 나뉩니다.
이 문제를 해결하려면 숫자의 최하위 비트, 즉 숫자의 마지막 자릿수부터 시작해야 합니다. 여기에서 우리는 3으로 나누어 떨어지는 가장 작은 수를 찾을 것입니다. 그런 다음 이를 기반으로 개수를 업데이트합니다.
예 - arr[i]가 3으로 나누어 떨어지는 숫자를 만들면 개수를 늘리고 숫자의 다음 자리로 이동합니다. arr[i]가 3으로 나누어지지 않으면 다음 숫자와 결합하여 3의 배수인지 확인합니다.
3의 배수 - 숫자의 자릿수가 3의 배수이면 3의 배수입니다.
예시
솔루션 구현을 보여주는 프로그램
#include <bits/stdc++.h>
using namespace std;
int countMaximum3DivisibleNumbers(string number){
int n = number.length();
vector<int> remIndex(3, -1);
remIndex[0] = 0;
vector<int> counter(n + 1);
int r = 0;
for (int i = 1; i <= n; i++) {
r = (r + number[i-1] - '0') % 3;
counter[i] = counter[i-1];
if (remIndex[r] != -1)
counter[i] = max(counter[i], counter[remIndex[r]] + 1);
remIndex[r] = i+1;
}
return counter[n];
}
int main() {
string number = "216873491";
cout<<"The number of 3 divisible number created by cutting "<<number<<" are : " <<countMaximum3DivisibleNumbers(number);
return 0;
} 출력
The number of 3 divisible number created by cutting 216873491 are : 5