백준 2846번 [오르막길](C++) -yes6686- 티스토리

백준 문제 풀이: 2846 (오르막길)

---

문제 링크: https://www.acmicpc.net/problem/2846

문제 설명:

수열이 주어졌을 때, **오르막길**의 최대 높이를 구하는 문제입니다. 오르막길은 연속해서 수가 증가하는 구간이며, **높이**는 그 구간의 마지막 값에서 시작 값을 뺀 값입니다. 주어진 수열에서 가장 높은 오르막길의 높이를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[1001]; // 수열을 저장할 배열

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

    int n; // 수열의 길이
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // 수열 입력
    }

    int s = 0; // 오르막길 시작점
    int ans = 0; // 최대 오르막길 높이

    for (int i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1]) { // 오르막길인 경우
            if (s == 0) { 
                s = arr[i - 1]; // 오르막길 시작점 기록
            }
            // 마지막 원소까지 도달한 경우 높이 계산
            if (i == n - 1) {
                ans = max(ans, arr[i] - s);
            }
        } else { // 오르막길이 끝난 경우
            if (s != 0) {
                ans = max(ans, arr[i - 1] - s); // 현재 오르막길의 높이 계산
            }
            s = 0; // 시작점 초기화
        }
    }

    cout << ans << '\n'; // 결과 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• 오르막길 탐색: 수열을 순회하면서 **연속 증가 구간**을 찾습니다.
• 시작점과 높이 계산:
  • 오르막길 시작점 s를 기록하고, 현재 높이를 계산합니다.
  • 오르막길이 끝나거나 마지막 원소에 도달하면 최대값을 갱신합니다.
• 종료 조건: s가 0이면 오르막길이 아니므로 새로 시작합니다.

세부 구현:

• if (arr[i] > arr[i - 1]): 오르막길인지 확인합니다.
• ans = max(ans, arr[i] - s): 현재 오르막길의 높이를 계산하고 최대값을 갱신합니다.
• s = 0: 오르막길이 끝나면 시작점을 초기화합니다.

시간 복잡도 분석

• 수열의 길이가 n일 때, 한 번만 순회하므로 시간 복잡도는 **O(n)**입니다.

---

결과

주어진 수열에서 가장 높은 오르막길의 높이를 정확히 출력합니다.

• 입력 예시:

  5  
  1 2 1 4 6

• 출력 예시:

  5

• 입력 예시:

  3  
  3 3 3

• 출력 예시:

  0

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!