백준 2491 <수열>

일반적으로 DP라고 생각하면 더욱 간단한 문제인 것 같다.

 

DP라고 해서 어렵게 생각하는 것이 아닌 이전까지의 값을 저장한다는 의미에서 DP가 될 것이다.

 

이 문제를 단순히 브루트 포스로 접근하게 되면 n*n 값으로 시간 초과가 날 가능성이 높다.

 

해결방법

1. 우선 오름차순 내림차순 두 번의 검사가 필요하다.
2.  check라는 int형 배열을 만든다 이 배열은 현재 지점까지 자신이 포함된 가장 긴 수열의 길이이다.
3. 오름 차순일 경우는 이전 값이 자기와 같거나 작으면 이전 check 값에 1 증가 아니면 1을 입력 (내림차순은 반대)
4. 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);

	}
}