[BOJ] 백준 20191. 줄임말 (Gold II)

학교 채점현황을 둘러보다가 발견한 문제.

KOI(한국정보올림피아드) 2020 고등부 2차대회 문제이기도 하다.

문제는 아래와 같다.

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

20191번: 줄임말

요약하자면, 문자열 T를 몇 번 반복해야 문자열 S와 T의 LCS가 문자열 S일지를 파악하는 문제이다.

---

의식의 흐름 및 해설

처음에는 해결 방법이 떠오르지 않았다.

생각보다 어려운 문제가 아닐까? 싶어서 출처를 확인하고, 티어도 확인해보았다. 골드2 정도의 문제였기 때문에 충분히 풀 수 있겠다 싶어서 좀 더 고민해보았다.

 

일단 문자열 T가 무한히 반복된다고 하자.

이 경우, 문자열 S의 문자가 문자열 T에 하나도 없지 않는 이상 -1을 출력할 일은 존재하지 않는다.

 

문자열 T가 몇 번 반복돼야 lcs가 문자열 S인지 구하는 문제이므로 S[1, i]의 문자열은 문자열 T를 몇 번 반복시켜야하는지를 메모이제이션해주어 dp값을 갱신해주는 방식으로 접근해보자.

 

이 접근법의 경우, S[1, i+1]의 문자열에 해당되는 답은 S[1, i]의 문자열의 dp값을 이용하여 답을 구할 수 있다.

S[1, i]의 문자열은, 문자열 T를 k번 반복시켜서 Tk의 idx번째에서 LCS를 구할 수 있었다고 하자.

S[1, i+1] 문자열은, 문자열 Tk의 idx+1번째부터 해서 Si+1문자가 있는지 찾아보고 없으면 k를 증가시킨 후에 인덱스를 찾으면서 dp값을 갱신해줄 수 있다.  

 

아래 예제에서 틀리지 않도록 주의하자.

akkkkkkk
kkka
ans: 4
wrong: 3

6%에서 틀려서 한참 헤매다가 결국 구글링을 했는데,

새로운 Ti로 넘어가고 나서 따로 인덱스를 구해주지 않으면 wrong에 해당되는 출력을 얻게 될 것이다.

이 예제를 왜 풀때는 생각하지 못했을까...

---

코드

#include <bits/stdc++.h>
#define sz(v) (int)v.size()
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int,pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 1e6+3;
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
string s,t;
vector<int> v[150];
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin>>s>>t;
    for(int i=0;i<t.size();i++){
        v[t[i]].push_back(i);
    }
    for(auto i:s){
        if(v[i].empty()){
            cout<<-1;
            return 0;
        }
    }
    int idx=-1, ans=1;
    for(auto i:s){
        auto it = upper_bound(all(v[i]), idx);
        if(it==v[i].end()){
            ans++;
            idx=-1;
            it = upper_bound(all(v[i]), idx);
        }
        idx=*it;
    }
    cout<<ans;
}

소문자의 아스키코드는 약 90 ~ 127임을 기억하자.

---

최근 우테코 블랙잭 미션, 체스 미션에서 할 일이 많았어서 백준을 거의 하지 못했었다.

우테코 방학 덕분에 오랜만에 난이도 있는 재밌는 문제를 풀어본 듯하다.

(사실 핑계고 백준보다 개발이 재밌어진 것 같다 ㅜㅜ)