<Baekjoon>#11053 가장 긴 증가하는 부분 수열 (Longest increasing subsequence) c++

링크텍스트

종만북 P.232 최대 증가 부분 수열 문제를 해결하는 완전 탐색 알고리즘을 공부하다가 도저히 이해가 안 돼서 일단 다른 사람들이 풀어 놓은 코드를 참고해서 코드를 작성했다.

idea

중첩 for문을 사용하여 A[i]의 값과 A[i] 이전의 값 A[j],
예를 들면 A[5]일 경우 A[0]부터 A[4]까지의 값과 비교해서
A[i]>A[j] (증가하는 부분수열)이고
dp[i]<dp[j]+1 현재 LIS길이 (dp[i])가 이전의 LIS길이 (dp[j])+1 보다 작다면 현재 LIS길이를 갱신해준다.

#include<iostream>
#include<vector>

const int MAX=1001;

using namespace std;

int lis3(const vector<int> &A) {
	
	int dp[MAX];
	int maxLen = 1;

	for (int i = 0; i < A.size(); i++) {
        dp[i]=1;
		for (int j = 0; j < i; j++) {
			if (A[i] > A[j] && dp[i] < dp[j]+1)
				dp[i] = dp[j] + 1;

			maxLen = max(maxLen, dp[i]);
		}
	}
	return maxLen;
}

int main() {
    int k;
	cin >> k;
	vector<int>A(k);
	for (int i = 0; i < k; i++)
		cin >> A[i];

	cout<<lis3(A)<<endl;

	return 0;
}

계속 c를 고집하다가 c++로 넘어오니까 좋다. 그런데 visual studio 에서는 컴파일 되는 것들이 백준에서는 컴파일 안 되는 게 많아서 최대한 다양한 컴파일러 환경에서 코딩 연습을 해야겠다.

**추가 궁금점

const int MAX=1001;
#define MAX 1001
두 개 선언하는 차이점을 찾아봤다.
const는 type 지정이 가능하고, 전역, 지역에서 사용 가능. 그리고 #define 을 사용할 경우 전처리기가 처리하기 때문에 버그 확인이 어렵다는 단점이 있다.