[백준 31235] 올라올라 [C/C++, Python]

문제

길이가 N인 수열 A가 주어질 때, N 이하의 양의 정수 k에 대하여 길이가 N - k + 1인 수열 B를 다음과 같이 정의하자.

수열 B가 감소하지 않도록 하는 k의 최솟값을 구해보자.

예를 들어 A = {3,1,4,2,5}이고 k = 2라면, B = {3,4,4,5}이므로 감소하지 않지만, k = 1이라면 B = {3,1,4,2,5}이므로 감소하는 부분이 존재한다. 이 경우 k의 최솟값은 2이다.

입력

첫째 줄에 수열 A의 길이 N이 주어진다. (1 <= N <= 10^6) 

둘째 줄에는 A(1),…, A(N)이 공백으로 구분되어 주어진다. (1 <= A(i) <= 10^9) 

입력으로 주어지는 모든 수는 정수이다.

출력

문제의 조건을 만족하는 N이하의 양의 정수 k 중 최솟값을 출력하라.

---

풀이

정수 k의 최솟값을 구하기 위해서는 수열 B가 감소하는 최장 구간의 길이를 구하면 된다.

수열 A에 대해 최댓값을 갱신해주며 이전 최댓값의 위치가 가장 먼 구간을 갱신해주면 K를 구할 수 있다.

최장 구간의 길이 K는 수열 A의 모든 요소들에 대해 수열 B를 구할 수 있는 충분한 수가 된다.

만약, 이전 최댓값보다 작은 경우가 아니라면, 최댓값을 갱신해주고, 구간의 길이 또한 1로 초기화 해주자.

---

소스코드 

C/C++

Python

---

출처

31235번: 올라올라