[25.03.24] ps study 백준 17841 UNIST는 무엇의 약자일까? (c++)

luke  · 

백준 17841 UNIST는 무엇의 약자일까?

17841 문제 바로가기
문제 정리
  1. 문자열이 여러개 들어온다.
  2. 앞에서 0글자 이상 5글자 이하로 뽑아서 unist라는 문자열을 만드는 개수를 구한다.
풀이 과정
  1. 문자열이 100000개고 각각 5번째 문자열까지 돈다 할 때 완전탐색하여 경우의 수를 알아내는 5^100000이 소요되는 풀이론 불가하다.
  2. 메모이제이션할 것을 정하면 dp로 풀 수 있을 법하다.
  3. 이차원 배열로 dp[각 문자들][완성된 문자 수] 로 저장할 수 있다.
  4. 문자열을 돌며 UNIST, NIST, IST, ST, T를 찾아 이전 문자열까지 만들어진 dp 배열에 더해주면 된다.
내 풀이

4번 내용을 점화식으로 풀면 dp[현재문자][완성된문자] = dp[이전문자][완성된문자] 로 볼 수 있다. UNIST
NIST
IST
ST
T
라는 문자열을 각각 입력으로 들어온 문자와 비교하는 게 핵심이다. i= 0->5, j=1->5-i 문자 확인을 위한 인덱스 k=0->j 로 두자. i+j 는 완성된문자의 개수를 나타낼 수 있고 j+k는 UNIST라는 문자열의 인덱스를 나타낼 수 있다.

제출한 코드
#include <bits/stdc++.h>
#define fastio cin.tie(NULL)->sync_with_stdio(0)
using namespace std;
const int mod = 1000000007;

int main()
{
    fastio;
    int n;
    cin >> n;
    vector<vector<int>> dp(n + 1, vector<int>(6, 0));
    dp[0][0] = 1;
    string unist = "UNIST";
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < 6; j++)
        {
            dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
        }
        for (int j = 0; j < 5; j++)
        {
            if (!dp[i - 1][j])
                continue;
            for (int add = 1; add <= 5 - j; add++)
            {
                bool valid = true;
                for (int k = 0; k < add; k++)
                {
                    if (s[k] != unist[j + k])
                    {
                        valid = false;
                        break;
                    }
                }
                if (valid)
                    dp[i][j + add] = (dp[i][j + add] + dp[i - 1][j]) % mod;
            }
        }
    }
    cout << dp[n][5] << "\n";
    return 0;
}