👓 문제 설명
남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.
이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.
돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?
💣 제한 사항
1 ≤ N ≤ 3×103 인 정수
- 1 ≤ Ai ≤ 108 인 정수
🚨 접근 방법
문제에 대한 설명이 모호해서
처음에 징검다리를 건널 수 있는 방법이 자기자신의 돌에서 바로 앞 돌로 한칸만 가는 줄 알았다.
즉, 999,1,2,3,4,5,6,7,8,9,1000이 있으면 999->1000으로 바로 이동하는 것이 불가능한 줄 알았다.
하지만 테스트케이스의 절반 이상이 계속 틀리다고 나와서 찾아보니 위 방법이 가능하다.
연속해서 이어지는 것이 아닌 불연속해서 이어져도 최대로 건널 수 있는 경우의 수를 찾아야했다.
N의 최대가 3x10^3이다. O(N^2)은 9x10^6이다. 약 10^7이므로 0.1초 걸린다.
그래서 이중 for문으로 dp를 이용하여 해결했다.
...앞으로 문제 잘 이해하자...
🚈 풀이
#include<iostream>
#include<vector>
using namespace std;
int main(int argc, char** argv)
{
// N의 최대가 3x10^3이다. O(N^2)은 9x10^6이다. 약 10^7이므로 0.1초 걸린다.
int n,high,answer=1;
vector<int>v;
cin>>n;
for(int i=0;i<n;i++){
cin>>high;
v.push_back(high);
}
vector<int>dp(n,1);
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
if(v[i]<v[j]){
dp[j]=max(dp[i]+1,dp[j]);
answer=max(answer,dp[j]);
}
}
}
cout<<answer;
return 0;
}