[백준] No.2491 - 수열 (C++)

문제

www.acmicpc.net/problem/2491

2491번: 수열

 

풀이

간단한 DP문제이지만 수열의 길이가 1인 경우의 예외 처리가 실수를 유발하는 듯하다.

 

우리가 현재의 숫자에서 확인해야 하는 것은 3가지 경우이다.

1. 다음 숫자가 더 큰 경우

2. 다음 숫자가 더 작은 경우

3. 다음 숫자와 같은 경우

 

본인의 경우 수열의 마지막 숫자부터 처음 숫자로 가는 역순으로 구성하였다.

 

cache값을 2차원 배열(cache[100000][2])로 선언하여

cache[idx][0]에는 현재의 숫자(idx)부터 시작하여 연속해서 커지는 수열의 길이 값을,

cache[idx][1]에는 현재의 숫자(idx)부터 시작하여 연속해서 작아지는 수열의 길이 값을 저장한다.

이후에는 역순으로 현재의 숫자(idx)에서 다음 숫자(idx+1)를 비교하여 아래와 같은 계산을 진행한다.

 

1번의 경우: if(arr[idx] < arr[idx+1])

커지는 길이 값 (cache[idx][0])의 값은 길이가 1 더 길어졌으므로 cache[idx+1][0] +1로 설정한다.

작아지는 길이 값 (cache[idx][1])은 다음 값이 더 크기 때문에 현재 숫자부터 재시작하여, 1로 설정한다.

 

2번의 경우: if(arr[idx]> arr[idx+1])

커지는 길이 값 (cache[idx][0])의 다음 값이 더 작기 때문에 현재 숫자부터 재시작하여, 1로 설정한다.

작아지는 길이 값 (cache[idx][1])은 길이가 1 더 길어졌으므로 cache[idx+1][1] +1로 설정한다.

 

3번의 경우: else

커지는 길이 값과 작아지는 값 모두 길이가 1 씩 길어지기 때문에 모두 cache[idx+1] +1값으로 설정해준다.

 

이후에는 cache[idx][0]과 cache[idx][1]값 중에

최대 길이값(max_length)보다 큰 경우 해당 값으로 재설정해주면서 진행하면 된다.

 

+ max_length은 수열의 길이가 최소 1 이상이기 때문에 초기에 1로 선언하여 준다.

코드