백준 2846번 오르막길

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

특별한 알고리즘을 요구하지 않는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 시작 위치를 정합니다.

2. 시작 위치를 기준으로 인덱스 하나씩 넘어가면서 자신보다 높은 위치이고 시작위치로부터 쭉 오르막길인지 확인합니다.

3. 오르막길이 아니면 바로 두 번째 for문을 탈출하여 여태까지 높이차를 구합니다.

4. 최대 높이차를 구합니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 1000;

 

int N;

int hill[MAX];

 

int maxHeight(void)

{

        int result = 0;

 

        for (int i = 0; i < N; i++)

        {

                 int start = hill[i]; //비교 시작하는 위치

                 int difference = 0; //높이 차

                 for (int j = i + 1; j < N; j++)

                 {

                         //start보다 해당 인덱스가 높은 위치에 있고 오르막길이라면

                         if (start < hill[j] && hill[j-1] < hill[j])

                                 difference = hill[j] - start; //높이 차 update

                         else //조건 해당하지 않는다면 끝낸다

                                 break;

                 }

                 result = max(result, difference); //제일 큰 높이차를 구해야한다

        }

        return result;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> hill[i];

 

        cout << maxHeight() << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~