[C++] Softeer : 징검다리

#include<iostream>
#include <vector>


using namespace std;

int N, H;
int cnt = 1; // 첫번째 돌 밟고 있음

int arr[3001];
int dp[3001] = {0};

int ans = 0;

int main(int argc, char** argv)
{
	scanf("%d", &N);

	for(int i = 0; i < N; i++){
		scanf("%d", &arr[i]);
		dp[i] = 1; // dp 1로 초기화, 모두 1번씩은 밟을 수 있음
	}

	// 무조건 좌에서 우로 탐색
	for(int i = 0; i < N; i++){
		for(int j = i; j < N; j++){
			if(arr[i] < arr[j] && dp[j] <= dp[i]){
				dp[j] = dp[i] + 1;
			}

			// for(int k = 0; k < N; k++){
			// 	printf("%d ", dp[k]);
			// }
			// printf("\n");
		}
	}

	for(int i = 0; i < N; i++){
		ans = max(ans, dp[i]);
	}

	printf("%d", ans);

	return 0;
}

진짜 오랜만에 푼 DP 문제. 다 까먹었다...
하나씩 비교하면서 가장 큰 경우를 찾는다. 전형적인 DP문제인데 엄청 헤맸네...