그랬었습니다

이 문제 역시 동적 계획법으로 푸는 문제다. 주어진 수열에서 일정 부분을 뽑아 가장 긴 증가수열을 만들고, 그 길이를 구하는 문제다. 이 문제에는 가장 심플한 규칙이 있다. v[i][0]이 i번째 수의 값이고, v[i][1]이 i번째 수의 값을 증가수열의 마지막 수로 잡았을 경우 가장 길게 만들 수 있는 증가수열의 길이라고 한다면, v[i][0] i)라면 v[i][1] < v[j][1]이다. 이 말이 무슨 말이냐면, 주어진 수열의 어떠한 값이 그보다 왼쪽에 있는 수열보다 크다면, 그 수를 마지막으로 하여 만들 수 있는 증가수열의 길이는 왼쪽에 위치한 그보다 작은 값을 마지막으로 하여 만들 수 있는 증가수열의 길이보다 길다. 라는 것이다. 따라서 풀이는 간단하다. 왼쪽에서부터 오른쪽으로 진행하면서 하나씩 ..