[Algospot] 최대 증가 부분 수열 (문제 ID : LIS)

문제

어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다.

어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.

어떤 수열의 각 수가 이전의 수보다 클 때, 이 수열을 순증가 한다고 한다.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열에 포함된 원소의 수 N (<= 500) 이 주어진다. 그 다음 줄에 수열이 N개의 정수가 주어진다. 각 정수는 1 이상 100,000 이하의 자연수이다.

 

출력

각 테스트케이스마다 한 줄씩, 주어진 수열의 가장 긴 증가 부분 수열의 길이를 출력한다.

---

어렵지 않은 동적 프로그래밍 문제인데 쉽게 보고 막 풀었다가 오류도 나고 고생햇다. for문을 두 번 돌리며 모두 조사해야한다. 만약 전보다 더 큰 값이 있다면 그 전까지의 dp값 +1과 비교해서 더 큰 값을 저장한다. 수열의 위치마다 dp값이 다르므로 max값을 계속 조사해서 마지막에 출력해야한다. 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/LIS.cpp

chosh95/STUDY

C++ 코드 

#include <iostream>
#include <memory.h>
#include <algorithm>
using namespace std;
int C, N;
int p[502];
int dp[502];

int main()
{
	cin >> C;
	while (C--) {
		cin >> N;
		memset(p, 0, sizeof(p));
		memset(dp, 0, sizeof(dp));	
		for (int i = 1; i <= N; i++) cin >> p[i];
		int res = 1;
		for (int i = 1; i <= N; i++) {
			dp[i] = 1;
			for (int j = 1; j < i; j++) {
				if (p[j] < p[i]) {
					if (dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
				}
			}
			res = max(res, dp[i]);
		}
		cout << res <<"\n";
	}
}