IM대비
백준 2491 <수열>
마이보
2020. 9. 19. 15:27
728x90

일반적으로 DP라고 생각하면 더욱 간단한 문제인 것 같다.
DP라고 해서 어렵게 생각하는 것이 아닌 이전까지의 값을 저장한다는 의미에서 DP가 될 것이다.
이 문제를 단순히 브루트 포스로 접근하게 되면 n*n 값으로 시간 초과가 날 가능성이 높다.
해결방법
- 우선 오름차순 내림차순 두 번의 검사가 필요하다.
- check라는 int형 배열을 만든다 이 배열은 현재 지점까지 자신이 포함된 가장 긴 수열의 길이이다.
- 오름 차순일 경우는 이전 값이 자기와 같거나 작으면 이전 check 값에 1 증가 아니면 1을 입력 (내림차순은 반대)
- check배열을 확인해서 가장 큰 값을 result값에 넣고 출력

오름 차순

내림 차순
전체 코드
더보기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
static int check[],num[],result,n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n=Integer.parseInt(br.readLine());
check=new int[n];
num=new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
num[i]=Integer.parseInt(st.nextToken());
}
check[0]=1;
for(int i=1;i<n;i++) {
if(num[i-1]<=num[i])
check[i]=check[i-1]+1;
else {
check[i]=1;
}
}
for (int i = 0; i < n; i++) {
result=Math.max(result,check[i]);
}
check[0]=1;
for(int i=1;i<n;i++) {
if(num[i-1]>=num[i])
check[i]=check[i-1]+1;
else {
check[i]=1;
}
}
for (int i = 0; i < n; i++) {
result=Math.max(result,check[i]);
}
System.out.println(result);
}
}