문제 설명
문자열 s와 정수 k가 주어졌다고 가정해 봅시다. 우리는 s에서 몇 개의 부분 수열(subsequence)을 선택하여 서로 다른 부분 수열 k개를 확보해야 합니다. 이때 하나의 부분 수열을 선택하는 비용은 (s의 길이) − (부분 수열의 길이)로 정의됩니다. 따라서 k개의 고유한 부분 수열을 선택했을 때 가능한 최소 총비용을 구해야 하며, 조건을 만족하는 집합을 찾을 수 없다면 -1을 반환합니다. 참고로 빈 문자열도 유효한 부분 수열로 간주합니다.
예를 들어 입력이 s = "pqrs", k = 4라면 출력은 3이 됩니다.
접근 방법
길이가 긴 부분 수열일수록 선택 비용이 작아지므로, 가능한 한 길이가 긴 부분 수열부터 우선적으로 선택하는 것이 유리합니다. 이를 위해 각 길이별로 만들 수 있는 고유한 부분 수열의 개수를 동적 계획법(DP)으로 계산한 뒤, 긴 길이부터 차례대로 소모하면서 총비용을 누적합니다.
여기서 중요한 점은 중복된 부분 수열을 세지 않도록 처리해야 한다는 것입니다. 이를 위해 각 문자가 마지막으로 등장한 위치를 기록하는 맵(last)을 사용하여, 같은 문자가 다시 나타날 때 이미 계산된 경우의 수를 빼줌으로써 중복을 제거합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다 −
n := s의 길이
크기가 (n + 1) × (n + 1)인 2차원 배열 dp를 정의하고 0으로 초기화합니다
맵 last를 하나 정의합니다
dp[0, 0] := 1
i := 0으로 초기화하고, i < n인 동안 i를 1씩 증가시키며 다음을 반복합니다 −
dp[i + 1, 0] := 1
j := (i + 1)로 초기화하고, j ≥ 1인 동안 j를 1씩 감소시키며 다음을 반복합니다 −
dp[i + 1, j] := dp[i, j] + dp[i, j − 1]
만약 s[i]가 last에 존재하지 않는다면 −
j := 0으로 초기화하고, j ≤ last[s[i]]인 동안 j를 1씩 증가시키며 다음을 반복합니다 −
dp[i + 1, j + 1] -= dp[last[s[i]], j]
last[s[i]] := i
cost := 0
i := n으로 초기화하고, i ≥ 0인 동안 i를 1씩 감소시키며 다음을 반복합니다 −
val := k와 dp[n, i] 중 최솟값
cost := cost + (val × (n − i))
k := k − dp[n, i]
만약 k ≤ 0이라면 −
반복문을 종료합니다
만약 k ≤ 0이라면 −
cost를 반환합니다
-1을 반환합니다
예제
더 나은 이해를 위해 다음 구현을 살펴보겠습니다 −
#include <bits/stdc++.h>
using namespace std;
int solve(string s, int k) {
int n = s.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
unordered_map<char, int> last;
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
dp[i + 1][0] = 1;
for (int j = (i + 1); j >= 1; j--) {
dp[i + 1][j] = dp[i][j] + dp[i][j - 1];
}
if (last.find(s[i]) != last.end()) {
for (int j = 0; j <= last[s[i]]; j++) {
dp[i + 1][j + 1] -= dp[last[s[i]]][j];
}
}
last[s[i]] = i;
}
int cost = 0;
for (int i = n; i >= 0; i--) {
int val = min(k, dp[n][i]);
cost += (val * (n - i));
k -= dp[n][i];
if (k <= 0) {
break;
}
}
if (k <= 0) {
return cost;
}
return -1;
}
int main(){
cout << solve("pqrs",4) << endl;
return 0;
}입력:
"pqrs", 4
출력
3
결과 분석
s = "pqrs"의 경우 모든 문자가 서로 다르므로, 길이 4짜리 고유한 부분 수열은 "pqrs" 하나뿐입니다(비용 0). 여기에 길이 3짜리 부분 수열 3개(예: "pqr", "pqs", "prs")를 추가로 선택하면 각각의 비용이 1이므로, 총비용은 0 + 1 × 3 = 3이 됩니다.