반응형
간단한 구현 문제였습니다.
풀이방법
오른쪽에서 봤을 때 가장 앞 원소는 오른쪽 끝에 있는 막대기고 이 막대기의 높이만큼 나머지 막대기를 볼 시야를 가리고 있습니다. 따라서 보이는 막대기의 수는 무조건 오른쪽 막대기부터 시작하여 높이를 확인해가면서 왼쪽 막대기를 보고, 오른쪽 막대기보다 왼쪽 막대기가 더 크다면 이 왼쪽 막대기는 보인다고 할 수 있습니다. 그렇다면 오른쪽 막대기부터 시작해 왼쪽 막대기로 순차적으로가며 오름차순인지를 확인한다고 볼 수 있습니다. 이렇게 보이는 왼쪽 막대기들 중 오름차순인 것들의 개수 + 가장 오른쪽 끝에 위치한 막대기의 개수를 해준것이 답이 됩니다.
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';
}
'Algorithm > Implementation' 카테고리의 다른 글
(C++) - 백준(BOJ) 11286번 : 절댓값 힙 답 (0) | 2020.10.03 |
---|---|
(C++) - 백준(BOJ) 9375번 : 패션왕 신해빈 답 (0) | 2020.10.01 |
(C++) - 백준(BOJ) 5430번 : AC 답 (0) | 2020.09.15 |
(C++) - 백준(BOJ) 1992번 : 쿼드트리 답 (0) | 2020.09.11 |
(C++) - 백준(BOJ) 18870번 : 좌표 압축 답 (2) | 2020.09.11 |