백준 2491번 C++ 풀이

https://www.acmicpc.net/problem/2491

2491번: 수열

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	실버 4

문제

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 이하의 정수이다.

출력

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

---

교내 대회를 준비하겠답시고 랜실디를 하겠다는 마음을 먹은게 무색하게, 학업은 내가 아무것도 못하게 만들었다. 대회 2일전, 이제서야 다시 풀자니, 아무래도 대회는 망할 것 같다는 느낌이 온다.

 

각설하고, 이번 문제는 가장 긴 증가/감소 부분 수열의 길이를 구하는 문제이다. N자체도 크지 않고, 원소를 교환하거나 값을 바꾸는 등, 복잡한 일이 들어가지 않기 때문에, 단순히 가장 긴 증가/감소 부분의 최대길이를 측정하고, 둘중 더 큰걸 출력하면 되는 아주 간단한 문제이다. 다만, 최대/최솟값을 저장할 변수의 초기값을 주의해야한다. 필자같은 경우는 처음에 음수로 설정했다가, 다음과 같은 반례 케이스로 인해 틀렸다.

 

1
1

 

이렇게 되면, 반복문을 통과하지 못하고, 반환하는 길이가 음수가 되기 때문에, 조심해야한다.

 

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

int n;
vector<int> v;

void input() {
    cin >> n;
    v.resize(n);
    for (int& x : v) cin >> x;
}

int getMaxIncrease() {
    // 길이값과, 최대값을 모두 1로 초기화. 이유는 설명했다.
    int len = 1, maxLen = 1;

    for (int i = 1; i < v.size(); i++) {
        // 만약 증가하지 않고, 꺾이는 부분이 발견되었다면 길이를 1로 초기화해서 다시 측정한다.
        if (v[i - 1] > v[i]) len = 1;
        else len++;
		
        maxLen = max(len, maxLen);
    }

    return maxLen;
}

int getMaxDecrease() {
    int len = 1, maxLen = 1;

    for (int i = 1; i < v.size(); i++) {
        // 만약 감소하지 않고, 꺾이는 부분이 발견되었다면 길이를 1로 초기화해서 다시 측정한다.
        if (v[i - 1] < v[i]) len = 1;
        else len++;

        maxLen = max(len, maxLen);
    }

    return maxLen;
}

void sol() {
    #ifndef BOJ // 테스트용 출력 코드. 제출시에는 이부분이 컴파일되지 않는다.
    cout << "inc: " << getMaxIncrease() << endl ;
    cout << "dec: " << getMaxDecrease() << endl;
    #endif

    cout << max(getMaxIncrease(), getMaxDecrease());
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    sol();
}