3333. Find the Original Typed String II - Streak 9

주의: k가 "최소" 이다.
엘리스는 k개 이상의 문자를 입력하려고 했었다는 뜻이다.

몇가지 용어를 먼저 정의해두자.

• 문자 그룹: 문자가 바뀌기 전까지의 연속된 문자
• 문자 그룹의 문자 타입: 문자 그룹을 형성하는 문자
• k - 문자 그룹의 수 = 실제로 경우의수를 만드는 선택가능한 수

 

함수를 정의해보자.

 

f(현재 문자 그룹, 남은 선택 수)

독립변수

• 현재 문자 그룹 i: 몇 번째 문자 그룹인가?
• 남은 선택 수 x: 몇 개의 문자를 더 채워야 하는가?

종속변수

• i 문자 그룹부터 x개의 문자를 더 채워야할 때, 지금까지 채워온 경우의 수

점화식을 세워보자.

초기조건은 다음과 같이 설정 가능하다.
x = [1, tg[0]]에 대하여

이 연산에 모듈로를 씌워주면 답을 구할 수 있다.

i < 2000, x < 500000
총 10억 개의 정수를 보관해야 하므로, 약 8GB의 메모리가 필요하다.

너무 비효율적이다...

좀 더 좋은, 수학을 이용한 풀이가 없을까?

앞에서 다 털면 뒤에서 못쓰기 때문에, 앞에서 턴 갯수를 알고 있어야 하긴 하는데

---

다시 한번 문제를 재정의해보자.

1. tgCount >= k

이면, 제약이 자동으로 만족하므로, 답은

2. tgCount < k

이 경우에는 만든 문자열이 k보다 짧을 수 있으므로,
전체 길이 < k인 경우 (나쁜 경우)를 세서 전체 경우의 수에서 빼주자.

---

f(현재 문자 그룹, 남은 선택 수)

독립변수

• 현재 문자 그룹 i: 몇 번째 문자 그룹인가?
• 남은 선택 수 x: 몇 개의 문자를 더 채워야 하는가?

종속변수

• i 문자 그룹부터 x개의 문자를 더 채워야할 때, 지금까지 채워온 경우의 수

여기서 “남은 선택 수 x”는 각 그룹에서 최소 1개씩은 이미 뽑았다고 보고, 그 이후에 추가로 더 뽑아야 하는 개수를 의미하도록 두자.
그러면 한 그룹에서 추가로 뽑을 수 있는 범위는 0 ~ (그룹 길이 - 1)이 된다.

 

 

즉, 우리는 전체 길이 ≤ k-1 인 결과만을 찾고, 그걸 최대 결과에서 제거해주면 된다.
이러면, 탐색해야 하는 범위가 대폭 줄어든다(k 이하).

 

 

이 관점에서 “전체 길이 ≤ k-1”을 세려면,

• “각 그룹에서 최소 1개씩 뽑은 뒤 추가로 채운 총합”이 0 ~ (k−1)−(문자 그룹의 수) 이하여야 한다.

다시, 점화식

점화식

초기조건

이때, 누적합을 이용해 이전 인덱스의 값을 구할 때 사용했던 값들을 재이용하면 더욱 빠르게 계산할 수 있다.

public class Solution {
    static final int MOD = 1_000_000_007;

    public int possibleStringCount(String word, int k) {
        int n = word.length();

        List<Integer> tg = new ArrayList<>();
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (word.charAt(i) == word.charAt(i - 1)) cnt++;
            else { tg.add(cnt); cnt = 1; }
        }
        tg.add(cnt);

        int groupCount = tg.size();
        long totalLen = n;
        long allWays = 1;
        for (int len : tg) allWays = (allWays * len) % MOD;

        if (k <= groupCount) return (int) allWays;
        if (k > totalLen) return 0;

        int maxX = (k - 1) - groupCount;

        int[] prev = new int[maxX + 1];
        int[] curr = new int[maxX + 1];

        int firstMax = Math.min(maxX, tg.get(0) - 1);
        for (int x = 0; x <= firstMax; x++) prev[x] = 1;

        for (int i = 1; i < groupCount; i++) {
            Arrays.fill(curr, 0);
            int window = tg.get(i);

            long windowSum = 0;
            for (int x = 0; x <= maxX; x++) {
                windowSum += prev[x];
                if (windowSum >= MOD) windowSum -= MOD;
                if (x - window >= 0) {
                    windowSum -= prev[x - window];
                    if (windowSum < 0) windowSum += MOD;
                }
                curr[x] = (int) windowSum;
            }

            int[] tmp = prev;
            prev = curr;
            curr = tmp;
        }



        long bad = 0;
        for (int x = 0; x <= maxX; x++) {
            bad += prev[x];
            if (bad >= MOD) bad -= MOD;
        }

        long ans = (allWays - bad) % MOD;
        if (ans < 0) ans += MOD;
        return (int) ans;
    }
}

문제를 처음부터 정확히 읽자