[KOI 2019 1차대회][초등부1번] 막대기

문제:

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

17608번: 막대기

 

문제 해석:

위 그림과 같이 n번선분부터 시작해 1번 선분까지 보면서 --> for(int i=n; i>=1; i--)

현재의 최대 높이(maxH) 보다 높은 선분(i번선분)을 발견했을때 최대높이를 갱신함과 동시에 답의 갯수증가를 해준다.

 

여기서 n번 선분이 시작 당시에 최대높이인것이 자명함으로 최대높이를 n번선분으로 초기화, 답의 갯수를 1로 초기화

후에 [n-1...1]번 선분을 보는 방법이있고 

 

모든 선분이 1이상임으로 최대높이를 0으로 초기화, 답의 갯수를 0으로 초기화 후에

[n...1]번 선분을 보는 방법이있다.

 

반복문 들어가기전 최대높이 초기화를 어떻게할 것인가의 차이점이 있을뿐 같은 메커니즘이다.

 

시간복잡도 분석:

n번 선분을 시작으로 1번선분까지 높이검사하는 1중 반복문에 지배되기때문에 O(N) 이다.

 

 

코드:

#include<bits/stdc++.h>
 
using namespace std;
 
const int MAX_N = 1e5;
int arr[MAX_N+1];
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, ans = 1;
    cin >> n;
    for(int i=1; i<=n; i++) cin >> arr[i];
    int maxH = arr[n];
    for(int i=n-1; i>=1; i--){
        if(arr[i] > maxH){
            ans++;
            maxH = arr[i];
        }
    }
 
    cout << ans;
    return 0;
}