백준17608 막대기

작성일 | In

문제 출처

  • 2019 KOI 1차 초등부 1번

시간복잡도

  • O(N)

풀이

오른쪽부터 보면서 최댓값이 갱신될 때 마다 정답을 증가시키면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

vector<int> v;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; v.resize(n);
	for(int i=0; i<n; i++){
		cin >> v[i];
	}
	int now = 0;
	int ans = 0;
	for(int i=n-1; i>=0; i--){
		if(v[i] > now){
			now = v[i]; ans++;
		}
	}
	cout << ans << "\n";
}