[백준 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 

 

 

 

소스코드 :