(C++) - 백준(BOJ) 17608번 : 막대기 답

www.acmicpc.net/problem/17608

17608번: 막대기

간단한 구현 문제였습니다.

 

풀이방법

 오른쪽에서 봤을 때 가장 앞 원소는 오른쪽 끝에 있는 막대기고 이 막대기의 높이만큼 나머지 막대기를 볼 시야를 가리고 있습니다. 따라서 보이는 막대기의 수는 무조건 오른쪽 막대기부터 시작하여 높이를 확인해가면서 왼쪽 막대기를 보고, 오른쪽 막대기보다 왼쪽 막대기가 더 크다면 이 왼쪽 막대기는 보인다고 할 수 있습니다. 그렇다면 오른쪽 막대기부터 시작해 왼쪽 막대기로 순차적으로가며 오름차순인지를 확인한다고 볼 수 있습니다. 이렇게 보이는 왼쪽 막대기들 중 오름차순인 것들의 개수 + 가장 오른쪽 끝에 위치한 막대기의 개수를 해준것이 답이 됩니다.

 

Code

#include <iostream>
using namespace std;
int stick[100000];
int n;
int answer = 1;
int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> stick[i];
    int pivot = stick[n-1];
    for(int i = n-2; i >= 0; i--)
        if(stick[i]>pivot) 
            answer++, pivot = stick[i];
    cout << answer <<'\n';
}