본문 바로가기

Algorithm/Implementation

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

반응형

www.acmicpc.net/problem/17608

 

17608번: 막대기

아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로

www.acmicpc.net

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

 

풀이방법

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

 

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';
}