이 글에서는 숫자로만 이루어진 문자열이 주어졌을 때, 이를 정수 값으로 해석하여 6으로 나누어 떨어지는 부분 문자열이 총 몇 개인지 구하는 문제를 다룹니다. 입력은 숫자(정수)로 구성된 문자열 형태이지만, 나눗셈 가능 여부는 반드시 정수 값 기준으로 판단해야 하며, 문자의 ASCII 값을 사용해서는 안 된다는 점에 유의하세요.
문제 예시
입력
str = "648"
출력: 3
설명: 부분 문자열 "6", "48", "648"이 각각 6으로 나누어 떨어집니다.
입력
str = "38342"
출력
4
설명: 부분 문자열 "3834", "342", "834", "42"가 각각 6으로 나누어 떨어집니다.
방법 1: 브루트 포스(완전 탐색)
가장 직관적인 방법은 가능한 모든 부분 문자열을 생성한 뒤, 각각이 6으로 나누어 떨어지는지 일일이 검사하는 것입니다. 조건을 만족하면 카운트를 1씩 증가시키면 됩니다. 구현은 간단하지만 모든 (i, j) 쌍에 대해 부분 문자열을 확인해야 하므로 시간 복잡도가 O(n²)이며, 문자열이 길어질수록 실행 시간이 급격히 늘어난다는 단점이 있습니다.
구현 예시
#include <bits/stdc++.h>
using namespace std;
int str_to_int(string str, int i, int j) {
int temp = 0;
for (; i <= j; i++) {
temp = temp * 10 + (str[i] - '0');
}
return temp;
}
int main() {
char str[] = "24661";
int n = strlen(str);
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = str_to_int(str, i, j);
if (temp % 6 == 0) count++;
}
}
cout << count << endl;
return 0;
}
실행 결과
6
방법 2: 동적 계획법(DP)을 활용한 효율적인 풀이
어떤 정수가 6으로 나누어 떨어지려면 다음 두 조건을 동시에 만족해야 합니다.
- 2의 배수: 마지막 자릿수가 짝수(0, 2, 4, 6, 8)여야 합니다.
- 3의 배수: 모든 자릿수의 합이 3으로 나누어 떨어져야 합니다.
이 성질을 활용하면 이미 계산된 결과를 저장·재활용하는 동적 계획법으로 문제를 선형 시간 안에 해결할 수 있습니다.
f(i, s)를 "i번째 인덱스부터 시작하는 부분 문자열 중, 자릿수 합을 3으로 나눈 나머지가 s가 되는 경우의 수"라고 정의하면, 전체 답은 Σi=0n-1 f(i, 0)이 됩니다.
문자열의 i번째 자릿수를 a라고 할 때, f(i, s) 상태에서는 i+1번째 위치부터 시작하는 짝수 부분 문자열들을 고려해야 합니다. 이때 (a + s)가 3으로 나누어 떨어지면 새로운 부분 문자열을 하나 더 만들 수 있습니다. 따라서 점화식은 다음과 같습니다.
f(i, s) = f(i + 1, (s + a) % 3) + ((a % 2 == 0) AND ((a + s) % 3 == 0))
구현 예시
#include <bits/stdc++.h>
using namespace std;
int find(int i, int s, char str[], int dp[][3]) {
// 문자열의 끝에 도달한 경우
if (i == strlen(str))
return 0;
// 이미 계산된 상태라면 저장된 결과를 반환
if (dp[i][s] != -1)
return dp[i][s];
int a = str[i] - '0';
int ans = ((a + s) % 3 == 0 && a % 2 == 0) + find(i + 1, (s + a) % 3, str, dp);
return dp[i][s] = ans;
}
int main() {
char str[] = "24661";
int n = strlen(str);
// 모든 상태를 저장할 DP 배열
int dp[n + 1][3];
memset(dp, -1, sizeof dp);
int count = 0;
for (int i = 0; i < n; i++) {
// 해당 위치의 문자가 '0'이면 카운트 증가
if (str[i] == '0')
count++;
// 이전까지의 자릿수 합을 3으로 나눈 나머지(0)를 넘겨 재귀 호출
else
count += find(i, 0, str, dp);
}
cout << "Number of substrings divisible by 6: " << count << endl;
return 0;
}
실행 결과
Number of substrings divisible by 6: 6
시간 복잡도: O(N) — 각 상태를 한 번씩만 계산하므로 완전 탐색 방식보다 훨씬 빠릅니다.
마무리
이 튜토리얼에서는 동적 계획법을 활용해 정수 문자열에서 6으로 나누어 떨어지는 부분 문자열의 개수를 구하는 방법을 알아보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있으며, 특히 입력 문자열이 길어질수록 완전 탐색 대비 압도적인 성능 차이를 보입니다. 이 글이 여러분의 학습에 도움이 되었기를 바랍니다.