[백준 2846] 오르막길 (C#, C++) - soo:bak

문제 링크

2846번 - 오르막길

설명

도로의 높이 수열이 주어지는 상황에서, 길이 N (1 ≤ N ≤ 1,000)과 각 지점의 높이(0 이상 1,000 이하의 정수)가 주어질 때, 가장 큰 오르막길의 크기를 구하는 문제입니다.

오르막길은 연속해서 높이가 증가하는 구간을 의미하며, 오르막길의 크기는 해당 구간의 시작 높이와 끝 높이의 차이입니다. 오르막길이 없으면 0을 출력합니다.

접근법

수열을 순회하며 연속 증가 구간을 추적합니다.

현재 높이가 이전 높이보다 크면 증가분을 현재 오르막길의 누적 크기에 더합니다. 높이가 감소하거나 같아지는 순간 오르막길이 끝나므로, 지금까지 누적된 오르막길 크기를 최대값과 비교한 후 누적값을 0으로 초기화합니다.

수열의 마지막까지 오르막길이 계속되는 경우를 처리하기 위해, 순회가 끝난 후 남은 누적값을 한 번 더 최대값과 비교합니다.

각 지점을 한 번씩만 확인하므로 시간 복잡도는 O(N)이며, 추가 공간은 O(1)입니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var heights = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);

      var maxClimb = 0;
      var currentClimb = 0;
      
      for (var i = 1; i < n; i++) {
        if (heights[i] > heights[i - 1]) {
          currentClimb += heights[i] - heights[i - 1];
        } else {
          maxClimb = Math.Max(maxClimb, currentClimb);
          currentClimb = 0;
        }
      }
      
      maxClimb = Math.Max(maxClimb, currentClimb);
      Console.WriteLine(maxClimb);
    }
  }
}

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 heights(n);
  for (int i = 0; i < n; i++)
    cin >> heights[i];

  int maxClimb = 0;
  int currentClimb = 0;
  
  for (int i = 1; i < n; i++) {
    if (heights[i] > heights[i - 1]) {
      currentClimb += heights[i] - heights[i - 1];
    } else {
      maxClimb = max(maxClimb, currentClimb);
      currentClimb = 0;
    }
  }
  
  maxClimb = max(maxClimb, currentClimb);
  cout << maxClimb << "\n";
  
  return 0;
}