문제
상근이는 자전거를 타고 등교한다. 자전거 길은 오르막길, 내리막길, 평지로 이루어져 있다. 상근이는 개강 첫 날 자전거를 타고 가면서 일정 거리마다 높이를 측정했다. 상근이는 가장 큰 오르막길의 크기를 구하려고 한다.
측정한 높이는 길이가 N인 수열로 나타낼 수 있다. 여기서 오르막길은 적어도 2개의 수로 이루어진 높이가 증가하는 부분 수열이다. 오르막길의 크기는 부분 수열의 첫 번째 숫자와 마지막 숫자의 차이이다.
예를 들어, 높이가 다음과 같은 길이 있다고 하자. 12 3 5 7 10 6 1 11. 이 길에는 2 개의 오르막길이 있다. 밑 줄로 표시된 부분 수열이 오르막길이다. 첫 번째 오르막길의 크기는 7이고, 두 번째 오르막길의 크기는 10이다. 높이가 12와 6인 곳은 오르막길에 속하지 않는다.
가장 큰 오르막길을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 상근이가 측정한 높이의 수이자 수열의 크기인 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수 Pi(1 ≤ Pi ≤ 1000)가 주어진다. 각 숫자는 상근이가 측정한 높이이다.
출력
첫째 줄에 가장 큰 오르막길의 크기를 출력한다. 만약 오르막길이 없는 경우에는 0을 출력한다.
알고리즘 분류
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(){
int n;
scanf("%d",&n);
int *arr = (int*)malloc(sizeof(int)*n);
for(int i = 0 ; i < n ; i++)
scanf("%d",&arr[i]);
int max = 0;
int start = arr[0];
int end = arr[0];
for(int i = 1 ; i < n; i++){
if(end < arr[i]){
end = arr[i];
//printf("start : %d end : %d\n",start,end);
}
else{
if(max < end - start)
max = end - start;
//printf("max : %d \n",max);
start = arr[i];
end = arr[i];
}
}
if(max < end - start)
max = end - start;
printf("%d\n",max);
}구현 알고리즘의 경우, 규칙을 찾아서 코드를 작성해 문제를 해결해야 합니다. 규칙을 찾기 위해서는 머리 속에서 상상의 나라를 펼치는 것이 아니라 손으로 입력 변수별로 결과 값을 계산해보는 것이 가장 빠르게 규칙을 찾을 수 있는 방법입니다.
하지만 본 문제에서는 규칙을 찾을 필요가 없다.
단순히 처음부터 min 값과 max 값을 찾아 탐색을 진행하면서 오르막길 중 가장 큰 차이 값을 계산하면 된다. 이와같은 탐색 문제는 가장 쉬운 유형에 속한다고도 할 수 있으니, 비슷한 여러문제를 풀어보고 문제 출제 유형의 패턴을 알아보시길 바라겠습니다! 이상입니다!
