[BOJ] 수열 2491번 C++

 

 

문제

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라. 

예를 들어 수열 1, 2, 2, 4, 4, 5, 7, 7, 2 의 경우에는 1 ≤ 2 ≤ 2 ≤ 4 ≤ 4 ≤ 5 ≤ 7 ≤ 7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 수열 4, 1, 3, 3, 2, 2, 9, 2, 3 의 경우에는 3 ≥ 3 ≥ 2 ≥ 2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 또 1, 5, 3, 6, 4, 7, 1, 3, 2, 9, 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 2를 출력하여야 한다.

입력

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다. N은 1 이상 100,000 이하의 정수이다.

출력

첫째 줄에 가장 긴 길이를 출력한다.

 

접근 방식

 

먼저, 가장 먼저 생각했던 방식은 증가하는 수열이라면 양수로, 감소하는 수열이라면 음수로 dp배열을 저장한 뒤

가장 큰 절대값을 찾는 식으로 생각했다

하지만, 문제는 

4 1 3 3 2 2 9 2 3

다음과 같은 입력이 있을 때 출력이 4여야 하는데

3이 되어버리는 문제가 생겼다

이유는 3 3 2 2 가 가장 긴 수열인데

처음 3 3이 증가인지 감소인지 모르기 때문이다.

 

그래서 오히려 더 단순히 생각했더니 풀렸다

따로 dp 배열을 만들지 않고

증가하는 수열의 길이, 감소하는 수열의 길이를 저장하는 변수를 만들어

각각의 경우에 각 변수를 증가시키고

만약 2 2와 같이 증가도 감수도 아닐때는 두 변수의 길이를 함께 증가시켜 주면된다..!

 

생각보다 어렵지만 또 생각해보면 어렵지 않았던 문제(마치 따뜻한 아이스아메리카노 같은 문제다 ^^)

 

코드

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> v(N);
    for (int i = 0; i < N; i++) cin >> v[i];

    int inc_len = 1, dec_len = 1, ans = 1; 
    for (int i = 1; i < N; i++) {
        if (v[i] > v[i - 1]) {
            inc_len++;
            dec_len = 1;
        } else if (v[i] < v[i - 1]) {
            dec_len++;
            inc_len = 1;
        } else {
            inc_len++;
            dec_len++;
        }
        ans = max(ans, max(inc_len, dec_len));
    }

    cout << ans << '\n';
    return 0;
}