백준 2491 - 수열(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2491

2491번: 수열

증가하는 수열 or 감소하는 수열을 둘 다 확인할 때, 가장 긴 길이를 확인하는 문제입니다.

 

2개의 수열을 확인해야하니 2차원 배열을 이용해서 풀었습니다.

 

처음 1번은 길이가 둘 다 1이니 1로 저장한 뒤,

다음 값부터 비교해주기 시작합니다.

1. 다음 값이 이전값보다 클 때 -> 증가하는 값을 1을 더한다, 감소하는 값을 1으로 바꾼다.

2. 다음 값이 이전값보다 작을 때 -> 증가하는 값을 1로 바꾼다, 감소하는 값을 1 더한다.

3. 같을 때 -> 2가지 경우다 1을 더한다.

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

int N;
int arr[100001];
int dx[100001][2]; // 0 -> up  1 -> down

void solve(){
    dx[1][0] = 1;
    dx[1][1] = 1;
    for(int i = 2; i <= N; i++){
        if(arr[i] > arr[i-1]){
            dx[i][0] = dx[i-1][0] + 1;
            dx[i][1] = 1;
        }
        else if(arr[i] < arr[i-1]){
            dx[i][1] = dx[i-1][1] + 1;
            dx[i][0] = 1;
        }
        else{
            dx[i][0] = dx[i-1][0] + 1;
            dx[i][1] = dx[i-1][1] + 1;
        }
    }
    int maxi = 0;
    for(int i = 1; i <= N; i++){
        maxi = max(maxi, dx[i][0]);
        maxi = max(maxi, dx[i][1]);
    }
    cout << maxi;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> arr[i];
    solve();
    return 0;
}

 

 

자세한 것은 코드를 참고해주세요.