백준 14437 - 준오는 심술쟁이!!

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

 

주어진 문자열은 사실상 장식이고 꽤 어려운 동적 계획법 문제이다. 이 포스트에서는 1차원 테이블과 슬라이딩 윈도우를 결합한 방법을 소개한다.

 

다음 테이블 2개를 정의한다.

 

dp_old(i) := 이전 인덱스 문자까지 총 i만큼의 숫자를 소진해서 문자열을 바꾸는 경우의 수

 

dp(i) := 현재 인덱스 문자까지 총 i만큼의 숫자를 소진해서 문자열을 바꾸는 경우의 수

 

이미 바꾼 문자는 다시는 바꿀 수 없으므로 이전 1~25만큼 바꿨을 때 문자열이 변하는 경우를 테이블에 반영하면서 전진하면 된다. 이때 처음 dp_old(0)은 공집합 1로 규정한다.

 

그리고 우리는 dp를 계산해야 되는데 문제의 k가 최대 25라는 조건이 있으므로 $dp(i) = \sum\limits_{x = i - 25}^{25} dp_{old}(x)$ 이와 같은 식을 계산하도록 한다.

 

여기서 추가 최적화가 필요한데 바로 문자를 1~25만큼 바꾸는 경우를 매 계산마다 일일이 더하지 않고 누적 합으로 관리하도록 한다. 누적합을 하지 않고도 정답을 받을 수 있다고 하니 참고하도록 한다.

 

누적합을 사용하면 인덱스 25까지는 그냥 더하면 되고 26부터 범위를 벗어난 값을 빼가면서 25 만큼의 곱셈 상수를 줄일 수 있다.

 

모든 i에 대해 계산을 하면 계산된 dp를 dp_old로 넘겨 다음 인덱스에 대한 테이블을 계산할 준비를 하도록 한다.

 

위 과정대로 동적 계획법을 수행하면 시간 복잡도 $O(s|N|)$ (N은 입력으로 주어진 문자열)으로 문제를 해결할 수 있다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
const int mod = 1e9 + 7;
 
int x;
string s;
int len;
vector<ll> window;
vector<ll> dp;
 
void solve()
{
  cin >> x >> s;
 
  window.resize(x + 1);
  dp.resize(x + 1);
  window[0] = 1;
 
  len = s.size();
  for (int i = 0; i < len; i++)
  {
    ll pref = 0;
 
    for (int j = 0; j <= min(25, x); j++)
    {
      pref += window[j];
      pref %= mod;
      dp[j] = pref;
    }
 
    for (int j = 26; j <= x; j++)
    {
      pref += window[j];
      pref -= window[j - 26];
      while (pref < 0) pref += mod;
      pref %= mod;
      dp[j] = pref;
    }
    window = dp;
  }
 
  cout << dp[x];
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록