[백준 17608] 막대기 (C#, C++) - soo:bak

문제 링크

17608번 - 막대기

설명

막대기들이 일렬로 세워져 있을 때, 오른쪽에서 보이는 막대기의 개수를 구하는 문제입니다.

접근법

오른쪽에서 보면 자기보다 오른쪽에 있는 막대기 중 더 높은 것이 없어야 보입니다.

오른쪽 끝에서부터 왼쪽으로 진행하면서 지금까지의 최대 높이를 기록합니다.

현재 막대기가 최대 높이보다 높으면 보이는 막대기이므로 개수를 늘리고 최대 높이를 갱신합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var h = new int[n];
    for (var i = 0; i < n; i++)
      h[i] = int.Parse(Console.ReadLine()!);

    var max = 0;
    var ans = 0;
    for (var i = n - 1; i >= 0; i--) {
      if (h[i] > max) {
        ans++;
        max = h[i];
      }
    }

    Console.WriteLine(ans);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi h(n);
  for (int i = 0; i < n; i++)
    cin >> h[i];

  int mx = 0, ans = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (h[i] > mx) {
      ++ans;
      mx = h[i];
    }
  }

  cout << ans << "\n";

  return 0;
}