[C++] 백준 2491:수열

문제링크

2491번: 수열

문제

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

출력

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

 

풀이

완전탐색을 이용하여 계속 증가하는 수열과 계속 감소하는 수열의 최대 길이 중 가장 긴 것을 출력해준다.

 

코드

#include <iostream>
#include <vector>
using namespace std;
 
int n;
 
int main(){
    ios::sync_with_stdio(0); 
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    
    int maxLength = 1;
    int tmp = 1;
 
    // 연속으로 커지는경우
    for (int i = 0; i < n - 1; i++) {
        if (v[i] <= v[i + 1]) {
            tmp++;
        }
        else {
            maxLength = max(maxLength, tmp);
            tmp = 1;
        }
    }
    // 계속 오름차순일 때 갱신하기 위한 코드
    maxLength = max(maxLength, tmp);
 
    tmp = 1;
    // 연속으로 작아지는경우
    for (int i = 0; i < n - 1; i++) {
        if (v[i] >= v[i + 1]) {
            tmp++;
        }
        else {
            maxLength = max(maxLength, tmp);
            tmp = 1;
        }
    }
    // 계속 내림차순일 때 갱신하기 위한 코드
    maxLength = max(maxLength, tmp);
 
    cout << maxLength;
 }

 

메모

원래 문제의 취지는 DP를 사용하는 것 같다. 이번 주말에 DP방법으로 다시 풀어봐야겠다.