막대기( BOJ 17608 )

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

17608번: 막대기

 

문제 파악하기

막대기를 일렬로 세운 후 오른쪽에서 바라보았을 때, 보이는 막대기의 개수를 출력하는 문제입니다. 오른쪽에서 보인다는 의미는 막대기의 높이가 오른쪽부터 순차적으로 증가해야 한다는 걸 말하며, 보이는 막대기의 총 개수를 구하기 위해서는 오른쪽부터 탐색을 시작하면 됩니다.

 

문제 해결하기

막대기가 보인다는 건 기존 가장 높았던 막대기보다 좀 더 크다는 의미입니다. 따라서, 지금까지 가장 높았던 높이보다 현재 막대기의 높이가 더 크면 오른쪽에서 봤을 때에도 보이게 되며, 보이는 막대기의 개수를 1개 늘려주면 됩니다. 이렇게 맨 오른쪽 막대기부터 시작해서 맨 왼쪽 막대기까지 진행하면 문제를 해결할 수 있습니다.

 

소스코드

#include <stdio.h>
#define NMAX 100010
 
int N;
int inp[NMAX];
 
int vmax, cnt;
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) scanf("%d", &inp[i]);
 
    for(int idx=N;idx>0;idx--) {
        if(vmax < inp[idx]) {
            vmax = inp[idx];
            cnt++;
        }
    }
 
    printf("%d", cnt);
}

후기

배열과 반복문을 사용하는 기본적인 문제입니다. 최댓값을 구하는 문제 다음으로 풀면 난이도가 적절하지 않을까 생각합니다.