[백준 17608번] 막대기

문제 링크

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

 

문제 요약

일렬로 세워진 막대기를 오른쪽에서 바라봤을 때, 보이는 막대기의 수를 구하는 문제이다. 

 

문제 풀이

주어진 막대기들을 오른쪽에서 왼쪽으로 하나씩 살펴보는 방법으로 문제를 해결할 수 있다. 오른쪽 끝의 막대기부터 시작해서, 현재까지 본 막대기들 중 가장 높은 것과 현재 막대기의 높이를 비교한다. 만약 현재 막대기의 높이가 지금까지 본 막대기들 중 가장 높은 막대기의 높이보다 크다면, 그 막대기는 오른쪽에서 봤을 때 보이는 막대기이다. 이 과정을 가장 왼쪽에 있는 막대기까지 반복하면, 오른쪽에서 봤을 때 보이는 막대기의 수를 구할 수 있다.

 

소스 코드

#include <stdio.h>

int n, A[100010];

int main() {
    scanf("%d", &n);
    
    for (int i = 0 ; i < n ; ++i) {
        scanf("%d", &A[i]);
    }
    
    int ans = 0, prev = -1;
    
    for (int i = n - 1 ; i >= 0 ; --i) {
        if (A[i] > prev) {
            ans += 1;
            prev = A[i];
        }
    }
    
    printf("%d\n", ans);
}