[백준 12352] Hedgemony (Large) (C#, C++) - soo:bak

문제 링크

12352번 - Hedgemony (Large)

설명

덤불 높이가 주어지고, 정원사가 왼쪽에서 오른쪽으로 이동하며 각 덤불을 양 옆 높이의 평균 이하로 깎을 때, N-1번째 덤불의 최종 높이를 구하는 문제입니다.

접근법

먼저 왼쪽에서 오른쪽으로 순회하며 각 덤불의 높이를 갱신합니다. 현재 덤불의 높이가 양 옆 평균보다 크면 평균으로 깎고, 아니면 그대로 둡니다.

이때 왼쪽 덤불은 이미 갱신된 값, 오른쪽 덤불은 아직 원래 값을 사용합니다. 최종적으로 N-1번째 덤불의 높이를 소수점 여섯째 자리까지 출력합니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var t = int.Parse(Console.ReadLine()!);
    for (var tc = 1; tc <= t; tc++) {
      var n = int.Parse(Console.ReadLine()!);
      var h = Array.ConvertAll(Console.ReadLine()!.Split(), double.Parse);

      for (var i = 1; i <= n - 2; i++) {
        var avg = (h[i - 1] + h[i + 1]) / 2.0;
        if (h[i] > avg)
          h[i] = avg;
      }

      Console.WriteLine($"Case #{tc}: {h[n - 2]:F6}");
    }
  }
}

C++

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

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

  int t; cin >> t;
  for (int tc = 1; tc <= t; tc++) {
    int n; cin >> n;
    vector<double> h(n);
    for (int i = 0; i < n; i++)
      cin >> h[i];

    for (int i = 1; i <= n - 2; i++) {
      double avg = (h[i - 1] + h[i + 1]) / 2.0;
      if (h[i] > avg)
        h[i] = avg;
    }

    cout << fixed << setprecision(6);
    cout << "Case #" << tc << ": " << h[n - 2] << "\n";
  }

  return 0;
}