[ 백준 BOJ ] 30805번 - 사전 순 최대 공통 부분 수열 (C++)

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

 

 

생각 흐름

• 여러 부분 수열 중 사전 순으로 진행되므로 가장 뒤에 올 수열은 가장 큰 수가 맨 앞에 있는 형태임을 인지
• 따라서 A와 B를 비교하며 가장 큰 수를 찾아줘야 하는데, 이 때 각각의 범위는 이전에 가장 큰 수를 찾았을 때의 A와 B 위치 +1 부터이어야 한다.
• while 문은 A와 B에서 찾아야 할 범위가 배열 크기를 넘어가거나, 해당 범위 내에서 같은 것을 찾지 못할 때 멈춰주면 된다.

 

 

#include <iostream>
#include <vector>

#define endl '\n'

using namespace std;

int N, M;
vector<int> A, B;

vector<int> validation(int i, int j){
    vector<int> v = {0,i,j};
    for(; i<N; i++){
        for(int h = j; h<M; h++){
            if(A[i]==B[h]){
                if(v[0]<A[i]){
                    v[0]=A[i];
                    v[1]= i+1;
                    v[2] = h+1;
                }
            }
        }
    }
    
    return v;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N;
    
    int tmp;
    for(int i = 0; i<N; i++){
        cin>>tmp;
        A.push_back(tmp);
    }
    
    cin>>M;
    
    for(int i = 0; i<M; i++){
        cin>>tmp;
        B.push_back(tmp);
    }
    
    vector<int> answer;
    
    int i=0, j=0;
    
    while(true){
        if(i>=N || j>=M) break;
        
        vector<int> v = validation(i, j);
        if(i==v[1] && j==v[2]) break;
        answer.push_back(v[0]);
        i = v[1];
        j = v[2];
    }
    
    cout<<answer.size()<<endl;
    for(int a : answer){
        cout<<a<<" ";
    }
    cout<<endl;
    
    return 0;
}