[14659번] 한조서열정리하고옴ㅋㅋ

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

알고리즘을 많이 공부하다보면 어떤 문제를 보게 되면 여러 알고리즘이 생각이 난다.

'이렇게 풀어보면 어떨까? 저렇게 풀어보면 어떻지?' 라는 생각이 많이 들게되고 결국 간단한 문제여도 어렵게 생각 할 수 있는 상황이 올 수 있다.

필자는 이 문제를 그렇게 생각하다가 당한 케이스이다. 시간 복잡도를 고려하며 문제를 어렵게 생각하다보니 해답이 산으로 가게 되었다.

하지만 생각외로 이 문제는 그냥 for문 한번을 통해 O(n)에 문제를 해결 할 수 있다.

현재 봉우리가 최대라고 생각했던 봉우리 보다 크면 지금까지 count했던 값을 갱신해주고, 

현재 봉우리가 최대라고 생각했던 봉우리 보다 작으면 계속해서 count+1을 해주며 진행해주면 문제를 해결 할 수 있다.

소스 코드 : 

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

#include <iostream> #include <cstdio> #include <algorithm>   using namespace std;   int arr[30002];   int main() {     int n;     scanf("%d", &n);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       int now = arr[0];     int ans = 0;     int cnt = 0;     for (int i = 1; i < n; i++)     {         if (arr[i] > now)         {             now = arr[i];             ans = max(cnt, ans);             cnt = 0;             continue;         }         cnt++;     }       ans = max(cnt, ans);     cout << ans << endl;     return 0; } //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus