백준 2846번 오르막길

https://www.acmicpc.net/problem/2846

문제

상근이는 자전거를 타고 등교한다. 자전거 길은 오르막길, 내리막길, 평지로 이루어져 있다. 상근이는 개강 첫 날 자전거를 타고 가면서 일정 거리마다 높이를 측정했다. 상근이는 가장 큰 오르막길의 크기를 구하려고 한다.

측정한 높이는 길이가 N인 수열로 나타낼 수 있다. 여기서 오르막길은 적어도 2개의 수로 이루어진 높이가 증가하는 부분 수열이다. 오르막길의 크기는 부분 수열의 첫 번째 숫자와 마지막 숫자의 차이이다.

예를 들어, 높이가 다음과 같은 길이 있다고 하자. 12 3 5 7 10 6 1 11. 이 길에는 2 개의 오르막길이 있다. 밑 줄로 표시된 부분 수열이 오르막길이다. 첫 번째 오르막길의 크기는 7이고, 두 번째 오르막길의 크기는 10이다. 높이가 12와 6인 곳은 오르막길에 속하지 않는다.

가장 큰 오르막길을 구하는 프로그램을 작성하시오.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
 
int num = 0, bottom = 0,top = 0;
int maxgap = 0;
int numarr[1004] = { 0, };
 
int main() {
    //freopen("test.txt", "r", stdin);
    cin >> num;
    for (int i = 0; i < num; i++) {
        cin >> numarr[i];
    }
 
    bottom = numarr[0];
    for (int i = 0; i < num; i++) {
        //cout << "현재바텀 : " << bottom << endl;
        if (numarr[i] < numarr[i + 1]) {
            top = numarr[i + 1];
            //cout << "현재탑 : " << top << endl;
        }
        else {
            if (maxgap < top - bottom) {
                maxgap = top - bottom;
                //cout << "최대차이는 : " << maxgap << endl;
            }
            top = 0;
            bottom = numarr[i+1];
        }
    }
    cout << maxgap;
}

이렇게 풀어주었습니다.

첫번째 인덱스를 가지고 바텀에 넣어준뒤에

그뒤의 요소와 비교를해서 크면 바텀은유지, 탑은 그다음큰값으로 쭉쭉 나아가게해서

같거나 다른수가나왔을때는 가장큰 오르막 경사와 비교를하여(gap) 최대 gap을 지정해줍니다.

그리곤 이미 오르막이 끝났다는 경우니, 탑을 초기화 시키고 그 끝난 다음의 요소를 바텀으로 지정해줍니다.

증가수열판단이 적용되는 문제라 생각됩니다.