Softeer 징검다리 c++

문제

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

 

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

 

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

제약조건

1 ≤ N ≤ 3×103 인 정수

1 ≤ Ai ≤ 108 인 정수

입력형식

첫 번째 줄에 돌의 개수 N이 주어진다.

두 번째 줄에 돌의 높이 Ai (1 ≤ i ≤ N)가 서쪽부터 동쪽으로 차례로 주어진다.

출력형식

첫 번째 줄에 철수가 밟을 수 있는 돌의 최대 개수를 출력하라.

풀이방법

 

이 문제는 전형적인 dp 문제이다. dp 문제를 정말 오랜만에 풀어보는 것 같다.

 

dp[n] = n번째 까지 오름차순으로 밟을 수 있는 돌의 최대 개수라고 하자.

dp[n+1] = if (arr[n] < arr[n+1] && dp[n]>dp[n+1] ) dp[n]+1이 된다

왼쪽부터 오른쪽까지 한번씩만 탐색하면 된다.

 

배열의 값이 더 크다는 것은 오름차순으로 밟을 수 있다는 것을 의미한다.

그리고 왼쪽부터 오른쪽으로 갱신하기 때문에 n번째 dp 값은 n 시점에 오름차순으로 밟을 수 있는 돌의 최대 개수가 된다.

 

코드

#include<iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <climits>
using namespace std;

int N;
vector<int> v;
int dp[3001];
int ans = -1;

int main(int argc, char** argv)
{
	cin>>N;
	for (int i=0;i<N;i++){
		int x;
		cin>>x;
		v.push_back(x);
		dp[i]=1;
	}
	
	for (int i=0;i<N;i++){
		for (int j=i;j<N;j++){
			if (v[i]<v[j] && dp[i]>=dp[j]){
				dp[j] = dp[i]+1;
			}
		}
	}
	for (int i=0;i<N;i++){
		ans = max(ans, dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

몇번 틀렸는데 dp 배열 크기 때문이었다. 문제조건을 왜 배열 크기가 10^3으로 봤을까 3*10^3 이었다