[백준/C++] 17608번: 막대기

문제 & 링크

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

 

풀이

1. 보는 방향, 즉 제일 오른쪽 막대기를 시작으로 잡는다.

2. 오른쪽에서 왼쪽으로 막대기를 탐색하며 지금까지 탐색한 막대기 중 가장 큰 것과 비교한다. (max값 구하는 알고리즘과 유사)

3. 더 큰 막대기가 있을 경우 count 변수를 증가시키고 가장 큰 막대기를 업데이트한다.

4. 2 - 3의 과정을 제일 왼쪽 막대기를 탐색할 때 까지 반복하고 최종 count를 출력한다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, h;
    
    cin >> N;
    
    vector<int> high(N);
    
    for (int i = 0; i < N; i++) {
        cin >> h;
        
        high[i] = h;       
    }
    
    int count = 0;
    int see = 0;
    for (int i = N - 1; i >= 0; i--) {
        if (high[i] > see) {
            count++;
            see = high[i];
        }
    }
    
    cout << count;
}