[백준 2491번] 수열 (java)

2491번: 수열

 

dp 2차원 배열을 이용하여 다이나믹 프로그래밍으로 문제를 해결하였다.

이 문제에서의 점화식은 다음과 같다.

 

• dp[n][0] : n번째 수열까지 중, 가장 긴 연속하는 증가하는 수열의 길이

• dp[n][1] : n번째 수열까지 중, 가장 긴 연속하는 감소하는 수열의 길이

 

수열의 n번째 수를 n-1번째 수와 비교한다.

 

n-1번째 수 < n번째 수 

n-1번째 수가 더 작으므로 오름차순이 유지가 된다. 유지가 된다는 것은 n-1번째까지의 가장 긴 증가하는 

수열의 길이(dp[n-1][0])에서 n번째 수 본인을 더한 길이인 dp[n-1][0] + 1가 dp[n][0]에 들어간다.

반면, 내림차순은 n번째 수가 n-1번째 수보다 더 크므로, n번째 수를 시작으로 하는 길이가 1인 

내림차순이 된다. 

 

dp[n][0] = dp[n-1][0] + 1

dp[n][1] = 1 

 

n-1번째 수 > n번째 수

n-1번째 수가 더 크므로 내림차순이 유지가 된다. n-1번째까지의 가장 긴 감소하는 수열의 길이(dp[n-1][1])에서 n번째 수  본인을 더한 길이인 dp[n-1][1] + 1가 dp[n][1]에 들어간다.

반면, 오름차순의 경우, n번째 수가 n-1번째 수보다 작으므로, n번째 수를 시작으로 하는 길이가 1인 

오름차순이 된다. 

 

dp[n][0] = 1

dp[n][1] = dp[n-1][1] + 1 

 

 

n-1번째 수 == n번째 수

n-1번째 수와 n번째 수가 같으므로 오름차순도 유지가 되고, 내림차순도 유지가 된다.

따라서 오름차순의 경우, n-1번째까지의 가장 긴 증가하는 수열의 길이(dp[n-1][0])에 1을 더한 값이 dp[n][0]가 되고, 내림차순의 경우, n-1번째까지의 가장 긴 감소하는 수열의 길이(dp[n-1][1])에 1을 더한 값이 dp[n][1]이 된다.

 

dp[n][0] = dp[n-1][0] + 1 

dp[n][1] = dp[n-1][1] + 1 

 

 

 

소스코드 : 

	import java.io.*;
	import java.util.*;
	public class n02491 {
	static int N;
	static int[] arr;
	static int[][] dp;
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	N = Integer.parseInt(br.readLine());
	arr = new int[N];
	dp = new int[N][2];
	String[] input = br.readLine().split(" ");
	for (int i = 0; i < N; i++)
	arr[i] = Integer.parseInt(input[i]);
	dp[0][0] = 1;
	dp[0][1] = 1;
	for (int i = 1; i < N; i++) {
	if (arr[i - 1] < arr[i]) {
	dp[i][0] = dp[i - 1][0] + 1;
	dp[i][1] = 1;
	}
	else if (arr[i - 1] > arr[i]) {
	dp[i][0] = 1;
	dp[i][1] = dp[i - 1][1] + 1;
	}
	else {
	dp[i][0] = dp[i - 1][0] + 1;
	dp[i][1] = dp[i - 1][1] + 1;
	}
	}
	int max = 0;
	for (int i = 0; i < N; i++) {
	max = Math.max(max, Math.max(dp[i][0], dp[i][1]));
	}
	bw.write(max + "\n");
	bw.flush();
	}
	}

view raw 2491.java hosted with ❤ by GitHub