[백준 17608번-C++] 막대기

http://acmicpc.net/problem/17608

{코드}

#include <iostream>
using namespace std;

int main() {
  int rods[100001], n;
  scanf("%d", &n);
  for (int i=0; i<n; i++) {
    scanf("%d", &rods[i]);
  }
  int max=rods[n-1], cnt=1;
  for (int i=n-2; i>=0; i--) {
    if (max < rods[i]) {
      max = rods[i];
      cnt++;
    }
  }
  printf("%d\n", cnt);
}

{설명}

이 문제에서는 모든 막대기를 일렬로 나열한 후 오른쪽에서 보기 때문에 어떤 막대기는 오른쪽에 있는 모든 막대기보다 크면 보이게 되는 것입니다.

우선, 가장 오른쪽의 막대기, 즉, 마지막 인덱스의 막대기는 무조건 보이므로 이를 max값으로 잡고 왼쪽으로 하나씩 이동하며 만약 이 max값보다 막대기의 길이가 더 크면 max를 업데이트하고 보이는 막대기 개수(cnt)를 1 증가시킵니다.

이렇게 모든 막대기의 길이를 다 확인하고 나면 총 보이는 막대기의 개수를 알 수 있습니다.