[알고리즘] 최대 선 연결하기

문제 내용

• 왼쪽의 번호와 오른쪽의 번호가 있는 그림에서 같은 번호끼리 선으로 연결하려고 합니다. 왼쪽번호는 무조건 위에서부터 차례로 1부터 N까지 오름차순으로 나열되어 있습니다. 오른쪽의 번호 정보가 위부터 아래 순서로 주어지만 서로 선이 겹치지 않고 최대 몇 개의 선을 연결할 수 있는 지 구하는 프로그램을 작성하세요.

구현 방식

• 가장 긴 오름차순을 푸는 문제와 동일하다.
• acc[k] 는 현재 k 번째 원소를 마지막으로 택해서 만들었을 때 올 수있는 최대 작대기 수를 의미한다.
• acc[k] 는 k 번째 이전의 원소들 중에서 ,
  • k 번째 원소 보다 작으면서 최대 작대기 수가 가장 큰 경우를 택했을 때가 해당된다.
• 점화식으로 나타내면 acc[k] = MAX( acc[i] + 1 ) (i 는 0~ k-1 까지, acc[i] < acc[k])

int DP(int N, vector<int>& numbers)
{
    vector<int> acc = vector<int>(N + 1, 1);
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (numbers[j] < numbers[i])
                acc[i] = max(acc[j] + 1, acc[i]);
        }
    }

    return *max_element(acc.begin(), acc.end());
}