Algorithm/Baekjoon

[Algorithm]Baekjoon 2491번 :: 수열

MaxLevel 2024. 1. 9. 04:22

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

 

2491번: 수열

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

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
 
int n;
int arr[100001] = { 0 };
int answer = 0;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    if (n == 1)
    {
        cout << 1;
        return 0;
    }
 
    int count = 1;
    int prevNum = arr[0];
 
    for (int i = 1; i < n; ++i)
    {
        if (arr[i] >= prevNum)
        {
            ++count;
        }
        else
        {
            count = 1;
        }
 
        prevNum = arr[i];
        answer = max(answer, count);
    }
 
    count = 1;
    prevNum = arr[0];
 
    for (int i = 1; i < n; ++i)
    {
        if (arr[i] <= prevNum)
        {
            ++count;
        }
        else
        {
            count = 1;
        }
 
        prevNum = arr[i];
        answer = max(answer, count);
    }
 
    cout << answer;
}
 cs

 

생각보다 정답비율이 낮아서 의아한? 문제.

연속된경우를 찾는거라서 N번의 시간복잡도로 끝낼 수 있다.