문제 설명
이 문제에서는 최대 105자리에 달하는 매우 큰 정수 하나가 주어집니다. 목표는 이 숫자를 여러 조각으로 잘랐을 때 3으로 나누어 떨어지는 조각의 개수가 최대가 되도록 하는 데 필요한 절단 횟수를 구하는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력 − 9216
출력 − 3
설명 − 숫자를 9|21|6처럼 세 조각으로 나누면, 세 조각 모두 3의 배수가 됩니다.
접근 방법
이 문제의 핵심은 누적 나머지(prefix remainder)를 활용하는 것입니다. 숫자를 왼쪽부터 오른쪽으로 한 자리씩 살펴보며, 현재 위치까지의 자릿수 합을 3으로 나눈 나머지를 계속 추적합니다.
서로 다른 두 위치에서 누적 나머지가 같다면, 그 사이 구간의 자릿수 합은 3으로 나누어 떨어진다는 뜻입니다. 따라서 해당 지점에서 절단하면 3의 배수인 조각을 하나 더 얻을 수 있습니다.
구체적인 알고리즘은 다음과 같습니다.
- 나머지 0, 1, 2 각각이 마지막으로 등장한 인덱스를 저장하는 배열을 준비하고, 나머지 0의 초기값을 미리 설정합니다.
- 왼쪽부터 한 자리씩 이동하며 누적 나머지 r을 갱신합니다.
- 나머지 r이 이전에 등장한 적이 있다면, 그 위치 이후부터 현재 위치까지의 구간은 3으로 나누어 떨어지므로 절단 카운트를 1 증가시킵니다.
- 현재 위치를 나머지 r의 최신 인덱스로 기록합니다.
참고로 3의 배수 판별법에 따르면, 어떤 수의 각 자릿수 합이 3으로 나누어 떨어지면 그 수 역시 3으로 나누어 떨어집니다. 이 성질 덕분에 전체 수를 직접 나누지 않고도 자릿수 합의 나머지만 추적하면 됩니다.
이 방식은 숫자의 길이를 n이라 할 때 O(n)의 시간 복잡도로 동작하므로, 105자리처럼 아주 큰 입력에서도 효율적으로 처리할 수 있습니다.
구현 예제
위 접근 방법을 C++로 구현한 프로그램입니다.
#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