[DP] sub-string 찾기

DP 연습 문제 : sub-string 찾기

문제

숫자로 이루어진 입력 문자열의 sub 문자열을 찾아 모두 더한 값을 출력하는 알고리즘을 작성하면 됩니다. 입력값인 숫자 $N$ 의 범위는 $1 \leq N \leq 2 \times 10^5$ 입니다.
더하는 값이 상당히 크기 때문에 sub 문자열의 합이 $T$ 라면, $T\ \% \ (10^9+7)$ 을 출력하면 됩니다.

예제 1

입력값

16

출력값

23

설명

숫자 16 의 sub 문자열은 16, 1, 그리고 6 이 있습니다. 모두 더하면 그 합은 23이 됩니다.

예제 2

입력값

123

출력값

164

설명

숫자 123 의 sub 문자열은 1, 2, 3, 12, 23, 123 이 있습니다. 모두 더하면 그 합은 164 가 됩니다.

문제를 이곳에서 풀어보세요.

---

정답 # 1

이 문제를 푸는 직접적인 방법은 주어진 문자열의 모든 sub 문자열을 생성하고 그것을 더하는 방식을 택하는 것입니다. 최악의 시나리오는, $N$ 의 최대값인 $2 \times 10^5$ 가 입력값으로 들어올때 발생합니다. len(N) 은 $N$ 이 문자열로 입력이 들어왔을때 문자열의 총 길이라 가정한다면, 이 $N$ 값의 sub 문자열을 구하기 위해서는

len(N) * (len(N) + 1) / 2

의 연산이 필요하고 이 연산은 약 $10^{10}$ 번의 연산으로 생각할 수 있습니다. $O(n^2)$ 의 시간복잡도 형태를 가지네요.

하지만 물론 이것이 문제를 푸는 솔루션의 전부는 아닙니다. 우리가 이 문제를 풀기 위해 필요한것은 부분 문자열이 아니라 부분 문자열들의 합을 찾는것이기 때문에, DP 를 적용한 솔루션은 선형 시간 복잡도 내에 이 문제를 해결할 수 있습니다.

알고리즘을 들여다보기 위해 $N = 5312$ 라는 예제 입력을 받았다고 가정하겠습니다.

가능한 모든 부분 문자열은 다음과 같습니다.

5 3 1 2 53 31 12 531 312 5312

이 부분 문자열을 특정 규칙에 의해 정리해 보겠습니다.

5 | 3 53 | 1 31 531 | 2 12 312 5312

특정 규칙이란 무엇인지 감이 오시나요? 위의 정렬된 모든 숫자들은 끝이 5, 3, 1 그리고 2 로 각각 끝나는 숫자들 끼리 모아놨습니다.

이제 이 모든 숫자들을 더하기 위해 DP 의 특징인 tabulation 을 적용해보겠습니다.
sd[i] 는 N[i] 로 끝나는 모든 숫자들의 합을 저장합니다.

sd[0] 은 N[0] = 5 로 끝나는 모든 숫자들의 합을 저장합니다.
sd[1] 은 N[1] = 3 로 끝나는 모든 숫자들의 합을 저장합니다.
sd[2] 은 N[2] = 1 로 끝나는 모든 숫자들의 합을 저장합니다.
sd[3] 은 N[3] = 2 로 끝나는 모든 숫자들의 합을 저장합니다.

S 가 최종 정답이라 한다면, 다음과 같습니다.

S = sd[0] + sd[1] + sd[2] + sd[3]

일반화 하자면, $S = \sum sd[i] \quad \forall \ 0 \leq i < len(N) $ 이 됩니다.

​sd[i] 를 찾았다고 가정하겠습니다. 이제 sd[i+1] 을 계산할 차례입니다. 어떻게 계산할까요?

예를 들어 sd[2] 를 찾았다고 해보겠습니다. $N = 5312$ 에서 sd[2] 는 N[2] = 1 이므로

sd[2] = 1 + 31 + 531 = 563 입니다.

sd[3] = 2 + 12 + 312 + 5312 이므로 sd[2] 를 구하기 위해 필요한 숫자들 끝에 2를 붙인것과 같습니다. 그렇기 때문에 다음과 같이 찾을 수 있습니다.

sd[3] = 2 + 12 + 312 + 5312
sd[3] = 2 + 10 + 2 + 310 + 2 + 5310 + 2
sd[3] = 4 * 2 + 10 * (1 + 31 + 531)
sd[3] = (3 + 1) * N[3] + 10 * sd[2]

일반화 하자면, 다음과 같습니다.

sd[i+1] = (i + 2) * N[i] + 10 * sd[i]
sd[0] = N[0]

$S$ 는 $N$ 이 커질수록 기하급수적으로 커질 수 있으므로, 문제에서 주어졌듯이 $S \ \% \ (10^9 + 7) $ 을 출력 해야되기 때문에 sd[i] 를 계산할때마다 modulo equivalence 를 적용합니다. 쉽게 말씀드리면 최종값에만 modulo($\%$) 를 적용하지 말고 모든 단계마다 적용하라는 의미가 됩니다.

다음은 위 설명을 적용한 솔루션 입니다.

#include<bits/stdc++.h>

using namespace std;
typedef unsigned long long LL;

#define MOD7 1000000007

string str;

int main()
{
    cin>>str;
    int l = str.length();
    
    LL outp = str[0] - '0'; 
    // 최종 출력값.

    LL temp = str[0] - '0'; 
    // str 문자열 변수의 인덱스 i 의 값으로 끝나는 모든 부분 문자열들의 합을 저장합니다. 

    for(int i=1 ; i< l ; i++)
    {
        temp = temp*10 + (i+1)*(str[i] - '0');
        temp = temp%MOD7;
        outp = (outp +temp)%MOD7;
    }
        cout<<outp<<endl;
    }
    return 0;
}

위 솔루션의 프로세스의 시간복잡도는 $O(len(N))$ 입니다. $len(N)$ 는 입력 문자열의 길이입니다.

---

정답 #2

비슷하지만 조금은 다른 방법으로 정답을 찾을 수 있습니다.

알고리즘을 설명하기 위해 정답 #1 과 같은 예시인 $N = 5312$ 을 예로 들겠습니다.

가능한 모든 부분 문자열은 다음과 같습니다.

5 3 1 2 53 31 12 531 312 5312

이제 각 숫자가 어느 자리수에 몇번 등장하는지 빈도수를 찾아보겠습니다.

	    천	  백	   십	 일
	----------------------
5	|    1	  1	   1     1	: 5312 & 531 & 53 & 5
3	|    0	  2	   2     2	: 5312, 312, & 531, 31 & 3, 53
1	|    0	  0	   3     3	: 12, 312, 5312 & 1, 31, 531 
2	|    0	  0	   0     4	: 2, 12, 312, 5312 

즉 최종 정답 $S$ 는 $S = 1111 * 5 + 111 * 3 * 2 + 11 * 1 * 3 + 1 * 2 * 4$로 계산됩니다.

다시 정리하면 다음과 같습니다. $S = 1111 * N[0] * 1 + 111 * N[1] * 2 + 11 * N[2] * 3 + 1 * N[3] * 4$ .

반복되는 형태가 보이시나요?

$len(N) = n$ 일때 $S$ 는 다음과 같이 계산됩니다.

$S =111 \cdots 11 \ (n \ times) * N[0] * 1 + 111\cdots 11 \ (n-1 \ times) * N[1] * 2 +$
$... + 111 * N[n-3] * (n-2) + 11 * N[n-2] * (n-1) + 1 * N[n-1] * n$

이 솔루션 역시 $S$ 는 $N$ 이 커질수록 기하급수적으로 커질 수 있으므로, 문제에서 주어졌듯이 $S \ \% \ (10^9 + 7) $ 을 출력 해야되기 때문에 매 step 마다 modulo equivalence 를 적용합니다.

다음은 위 설명을 적용한 솔루션 입니다.

#include <bits/stdc++.h>
#include <string>
#include <math.h>
using namespace std;

int substrings(string balls) {
	long long int result = 0;
	long long int dp = 1;
    
	for (long long int i=balls.length()-1; i>=0; i--){
		result += (dp * (balls[i]-'0') ) * (i+1);
		result %= 1000000007;
		dp = (dp * 10 + 1);
		dp %= 1000000007;
	}
	return result;
}

int main() {
    string balls;
    cin >> balls;
    long long int result = substrings(balls);
    cout << result << endl;
    return 0;
}

---