백준 2332, 전화번호

개요

문제 링크
골드 5, DP
연속된 부분 문자열의 최소 구성 횟수

---

접근

1. 접근 자체는 매우 쉽지만 구현이 까다로워서 실수하기 좋음

2. 길이 L이 100으로 작으므로 O(L×L×N) 수준에서 해결가능, N은 크므로 루프는 한 번만 돌려야하고, 루프를 돌 때 중심이 처음 문자열이 됨을 알 수 있음.

3. 문자열 루프를 돌면서 n개의 component 중 같은 것을 찾고, 만약 같다면 component의 길이만큼 뺀 위치의 값과 비교

4. dp[i-component_length]+1과 dp[i] 비교해서 최솟값으로 업데이트

5. 이때 마지막 출력 조건이 앞에서부터 component를 출력하는 것이므로 업데이트마다 앞이 어딘지, 어떤 component를 사용했는지 같이 업데이트 해야함.

   // 아래와 같다면
   ...1234....
    23
   // (3이 있는 위치의 길이)는 (1이 있는 위치의 길이)부터
   // 하나(23)만 추가해서 구성 가능함
   //
   // 따라서 (1이 있는 위치의 길이)+1과 비교 후
   // (길이, 앞=1이 있는 위치, 어떤=component(23)의 인덱스)를 업데이트

---

Pseudo code

for (i)
    for (j = i의 앞)
        for (component)
            // 1. component의 길이만큼 앞의 위치를 찾고
            if (component의 길이와 i-j가 다르면)
                continue
            // 2. 길이뿐 아니라 문자열도 동일한지 확인하고
            if (component와 j~i substring이 다르면)
                continue
            // 3. 더 크면 업데이트할 필요가 없으므로
            if (앞의 위치의 최대 길이 + 1이 현재 저장된 값보다 크면)
                continue
            dp[i].length = dp[j].length+1 // 길이
            dp[i].previous = j // 앞
            dp[i].component_index = index(component) // 어떤

---

Source code

#include <bits/stdc++.h>
using namespace std;

int dp[110][3];
int val[] = {2,2,2,3,3,3,4,4,1,1,5,5,6,6,0,7,0,7,7,8,8,8,9,9,9,0};

int compare(string a, string b) {
    for (int i=0; i<a.size(); i++)
        if (val[a[i]-'a']+'0' != b[i])
            return 1;
    return 0;
}

int main() {
    string a, s;
    int n;
    vector <string> p, q;
    cin >> a >> n;
    int m = a.size();
    for (int i=0; i<n; i++) {
        cin >> s;
        q.push_back(s);
    }
    for (int i=1; i<=m; i++) {
        dp[i][0] = 2e9;
        for (int j=0; j<i; j++) {
            for (int k=0; k<n; k++) {
                string x = q[k];
                if (x.size() != i-j)
                    continue;
                if (compare(x, a.substr(j, i-j)))
                    continue;
                if (dp[j][0]+1 >= dp[i][0])
                    continue;
                dp[i][0] = dp[j][0]+1;
                dp[i][1] = j;
                dp[i][2] = k;
            }
        }
    }
    int v = dp[m][0];
    if (v == 2e9) {
        cout << "0\nNo solution.";
        return 0;   
    }
    cout << v << '\n';
    for (int i=0; i<v; i++) {
        p.push_back(q[dp[m][2]]);
        m = dp[m][1];
    }
    for (int i=0; i<v; i++)
        cout << p[v-i-1] << "\n";
}