[BOJ 14659, C++] 한조서열정리하고옴ㅋㅋ

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

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

 

풀이

x번째 활잡이의 봉우리가 arr[x]이고, x < i 일 때

arr[x] > arr[i]이면 (x번째 활잡이가 잡을 수 있는 적의 숫자) += 1을 해주고

arr[x] <= arr[i]이면 답을 갱신해주고 x = i,  (x번째 활잡이가 잡을 수 있는 적의 숫자)  = 0으로 바꿔주고 위의 과정을 반복한다.

 

x에서 출발하여 처음으로 arr[x]보다 봉우리가 높은 곳을 arr[i]라고 할 때, x와 i사이에 숫자가 존재할 수도 있을 것이다.

x와 i 사이에 있는 값을 x + 1이라고 하면 x + 1번째 활잡이도 구해야 하는 것이 아닌가하는 생각이 드는데, arr[x+1]의 값은 arr[x]보다 작기 때문에 무조건 arr[x]값이 arr[x+1]보다 크게 될 수 있다는 것이 보장이 된다.

그러므로 바로 arr[x] <= arr[i]를 만나면 바로 i번째 활잡이가 잡을 수 있는 수를 구하면 된다.

 

코드

x = 내림차순 값들에서 가장 큰 값을 낼 수 있는 활잡이, val = x번째 활잡이가 처치할 수 있는 적의 수

#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int n, ans = 0, arr[30001];
 
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
 
    int x = 0, val = 0;
    for (int i = 1; i < n; i++) {
        if (arr[x] > arr[i]) val += 1;
        else {
            ans = max(ans, val);
            val = 0;
            x = i;
        }
    }
 
    cout << max(ans, val) << endl;
}