[C++] 사전 순 최대 공통 부분 수열

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

 

구현할 때 신경쓸 게 좀 많아서 번거롭다고 느낀 문제였다. 우선 나는 다음과 같이 구현하였다. 

 

일단 이 문제는 그리디로 풀 수 있다. 왜냐하면 구해야 하는 것이 "사전 순 최대" 공통 부분 수열이기 때문이다. 길이만 가장 길어야 하는 거면 dp로 풀어야 하지만, 사전 순으로 했을 때 가장 나중인 것을 선택하면 되므로 그리디하게 공통되는 최댓값을 쭉 선택하면 된다. 

 

다시 정리하자면, 공통되는 수 중 최댓값을 찾고, 그 수의 오른쪽을 기준으로 또 다시 공통되는 수 중 최댓값을 찾고... 를 반복하면 된다. 

 

구체적인 구현은 이렇다. 

 

우선 a 배열에서 최댓값을 찾는다. 찾은 최댓값이 b 배열에도 있는지 확인한다.

만약 없다면 아까 a 배열에서 최댓값을 찾은 범위와 동일한 범위를 다시 탐색하는데, 아까 찾은 최댓값보다 작은 값들 중에서 최댓값을 구한다. 그리고 다시 b 배열에 있는지 확인한다. 

만약 b 배열에 있었다면 정답에 추가해주고 a 배열과 b 배열의 인덱스를 증가시킨다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int m;
    cin >> m;

    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];

    vector<int> ans;

    int amaxi = 0;
    int amax = 0;
    int apremax = 1000;
    int bmaxi = 0;

    while (amaxi < n && bmaxi < m) {
        amax = 0;
        int atmpi = 0;
        bool afound = false;
        bool bfound = false;

        // a에서 최댓값 구하기 (이전에 구한 최댓값 이후 안에서)
        for (int i = amaxi; i < n; i++) {
            if (a[i] > amax && a[i] < apremax) {
                amax = a[i];
                atmpi = i;
                afound = true;
            }
        }

        // 해당 범위에서 찾지 못했으면 a 인덱스 증가하고 continue
        if (!afound) {
            amaxi++;
            continue;
        }

        // 방금 구한 a의 최댓값이 b에도 있는지 체크
        for (int i = bmaxi; i < m; i++) {
            if (b[i] == amax) {
                bmaxi = i + 1;
                ans.push_back(amax);
                amaxi = atmpi + 1;
                bfound = true;
                break;
            }
        }

        // b에서 못 찾았으면 다시 a로 가서 그거보다 작은 값들 중 최댓값 찾기
        if (!bfound) {
            apremax = amax;
        }
    }

    int ansn = ans.size();
    cout << ansn << '\n';
    if (ansn != 0) {
        for (int i = 0; i < ansn; i++) cout << ans[i] << ' ';
        cout << '\n';
    }
}

(AC)

---

 

[참고]

https://www.acmicpc.net/board/view/148187

https://testcase.ac/problems/30805