[백준 2491] 수열

🔗알고리즘 문제

간단한 dp문제이지만 처음에 너무 어렵게 생각하는 바람에 해결하는데 오래걸린 문제이다. 아직 dp에 관해서는 많이 부족하다고 느껴져 앞으로 어떻게 공부를 해야할지 고민이다..

문제 분석

이 문제는 주어지는 수열에서 연속해서 커지거나 작아지는 수열의 길이를 출력하는 문제이다.

예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2이 주어질 때 가장 긴 구간은 1, 2, 2, 4, 4, 5, 7, 7이 되므로 그 길이 8을 출력한다.

발상

dp문제라는 것에 집착하여 오히려 문제를 힘들게 해결한 케이스이다. 지금까지의 dp문제에서는 dp배열 속 값을 저장하고 그 값을 이용하여 해결하는 문제가 대다수여서 이 문제또한 dp배열을 이용하여 해결하려고 하였지만 반례를 해결하지 못하고 실패했다....

이 문제는 궁극적으로 연속해서 커지는 수열의 길이 / 연속해서 작아지는 수열의 길이만 알고있으면 쉽게 해결되는 문제이다. 두 값을 변수 A, B로 사용하여 문제를 해결해야겠다는 생각을 하였다.

알고리즘 설계

1. nums 배열에 값을 입력받는다.
2. for문을 진행하며 nums의 현재 인덱스의 값이 다음 값보다 크다면 A를 증가시켜준다.
   반면 nums의 현재 인덱스의 값이 다음 값보다 작다면 B를 증가시킨다.
3. 둘 값중 더 큰 값이 현재까지 진행된 수열에서의 정답이 된다.

코드

#include<iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n;
    int answer = 1;
    int up = 1;
    int down = 1;

    int nums[100001] = {};

    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }

    for(int i = 0; i < n - 1; i++){
        if(nums[i] >= nums[i + 1])
            up++;
        else
            up = 1;

        if(nums[i] <= nums[i + 1])
            down++;
        else
            down = 1;

        answer = max(answer, max(up, down));
    }

    cout << answer;
}