[백준 14335] 서로 다른 부분 수열의 개수 [Java]

문제

https://www.acmicpc.net/problem/14335

 

---

풀이

문자열 S에 대해 순서를 고려한 서로 다른 부분 수열의 수를 구하는 문제다.

문자열의 길이가 최대 1,000으로 모든 부분 수열들을 구하고 중복을 제거한다면 시간 초과가 발생한다.

순서를 고려하므로 중복되는 문자에 대한 부분 수열을 제거해야 한다.

dp[i] : i번까지 문자들로 만들어진 서로 다른 부분 수열의 수

중복을 고려하지 않고 부분 수열의 수를 기록하자.

            long[] dp = new long[N + 1];
            dp[0] = 1;
            
            for (int i = 1; i <= N; ++i) {
                dp[i] = (dp[i - 1] << 1);
            }
            sb.append(dp[N]).append('\\n');

이제 중복되는 요소를 제거해보자.

이전에 마지막으로 등장한 S[i - 1]의 위치를 j라고 하자.

현재 문자 S[i - 1]을 dp[i - 1]에 추가할 때 만들어지는 부분 수열은, dp[j - 1]에 S[i - 1]을 추가할 때 만들어진 부분 수열을 포함한다.

따라서 S[i - 1]이 등장한 적 있다면, **dp[i] = dp[i - 1] * 2 - dp[j - 1]**가 성립한다.

S[i - 1]이 마지막으로 등장한 이전 위치를 기록해줄 배열 prev와 함께 점화식을 수정하자.

            int[] prev = new int['z' + 1];
            Arrays.fill(prev, -1);

            for (int i = 1; i <= N; ++i) {
                final int j = prev[S[i - 1]];
                dp[i] = (dp[i - 1] << 1) - (j > -1 ? dp[j - 1] : 0);
                prev[S[i - 1]] = i;
            }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/14335.java

problem-solving/baekjoon-online-judge/normal/14335.java at main · rogi-rogi/problem-solving