[Softeer - Lv3] 징검다리

문제

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.

이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.

돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?

 

풀이

이 문제는 간단한 DP문제로 arr 배열을 쭉 받은 이후에 기본적으로 밟는 횟수인 1로 설정을 한다.

이후에 DP[i]와 DP[j]를 비교해서 arr[i]<arr[j]이고 dp[i]>=dp[j]이면 Dp[j]=DP[i]+1로 갱신한다.

 

코드

#include<iostream>
#include <vector>
using namespace std;
int arr[3001], dp[3001];

int main(int argc, char** argv)
{
    int n;
    cin >> n;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
        dp[i]=1;
	}

    int ans = 0;
	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 i = 0; i < n; i++){
		ans = max(ans, dp[i]);
	}

	printf("%d", ans);

	return 0;
}