BOJ 17841 : UNIST는 무엇의 약자일까?

• 문제 링크 : boj.kr/17841
• 난이도 : G3
• 태그 : DP

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector<pii> arr(n);
    string target = "UNIST";
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        pii curr = {0, 0};
        for(int i = 0; i < 5; i++) {
            if(s[0] == target[i]) {
                curr.first = i;
                break;
            }
        }
        for(int i = 0; i < 5 - curr.first; i++) {
            if(s[i] == target[i+curr.first]) {
                curr.second++;
            }
            else break;
        }
        arr[i] = curr;
    }
    vector<array<int, 5>> dp(n);
    for(int i = 0; i < 5; i++) {
        dp[0][i] = (arr[0].first == 0 && arr[0].second > i);
    }
    for(int i = 1; i < arr.size(); i++) {
        dp[i] = dp[i-1];
        if(arr[i].second == 0) continue;
        for(int j = 0; j < arr[i].second; j++) {
            int before = (arr[i].first == 0 ? 1 : dp[i-1][arr[i].first-1]);
            dp[i][arr[i].first+j] += before;
            dp[i][arr[i].first+j] %= 1000000007;
        }
    }
    cout << dp[n-1][4] % 1000000007;

    return 0;
}

---

풀이

문자열은 앞 5자리만 중요하다. 앞 5자리만 보고 (해당하는 부분문자열의 위치, 길이)로 전처리한다. ex) UNIXX -> (0, 3)

dp배열을 dp[보고있는 문자열][완성된 UNIST의 길이]로 놓고 구하면 된다.