[백준 알고리즘] 2846번: 오르막길
May 05, 2020
2846번: 오르막길
상근이는 자전거를 타고 등교한다. 자전거 길은 오르막길, 내리막길, 평지로 이루어져 있다. 상근이는 개강 첫 날 자전거를 타고 가면서 일정 거리마다 높이를 측정했다. 상근이는 가장 큰 오르막길의 크기를 구하려고 한다. 측정한 높이는 길이가 N인 수열로 나타낼 수 있다. 여기서 오르막길은 적어도 2개의 수로 이루어진 높이가 증가하는 부분 수열이다. 오르막길의 크기는 부분 수열의 첫 번째 숫자와 마지막 숫자의 차이이다. 예를 들어, 높이가 다음과 같은 길이 있다고 하자. 12 3 5 7 10 6 1 11. 이 길에는 2 개의 오르막길이 있다. 밑 줄로 표시된 부분 수열이 오르막길이다. 첫 번째 오르막길의 크기는 7이고, 두 번째 오르막길의 크기는 10이다. 높이가 12와 6인 곳은 오르막길에 속하지 않는다. 가장 큰 오르막길을 구하는 프로그램을 작성하시오.접근 방법:
탐색 알고리즘 아이디어를 생각했다. 탐색을 시작하는 출발 인덱스를 설정하고 내리막길을 만날때까지 인덱스를 증가시킨다. 내리막길을 만나면 오르막길의 끝 인덱스의 값과 출발 지점의 값의 차를 구해서 높이를 구하고 그 높이가 현재까지 구한 값들 중 최대 높이인지 확인한다. 탐색은 주어진 수열의 끝의 도달할때까지 진행하고 중복 탐색을 방지하기 위해서 한번 탐색이 끝나면 탐색 시작인덱스를 마지막으로 찾은 인덱스+1로 지정한다.
통과 코드:
#include <cstdio>
#include <vector>
using namespace std;
int main (){
vector <int> v;
int N, h, j=0;
int maxh = 0, i = 0, start = 0;
scanf("%d", &N);
for (int k = 0 ; k < N ; k++){
int p;
scanf("%d", &p);
v.push_back(p);
}
while(true){
if (v[i] < v[i+1]) i++; // 다음 숫자가 더 크면 그냥 이동 = 오르막길
else { // 내리막길에 들어서면
int h = v[i] - v[start]; // 출발점-현재지점으로 높이를 구한다.
if (maxh < h) maxh = h; // 최대높이 구하기
start = i+1; // 다시 탐색을 시작하는 시작점 잡아주기
i++; // 한칸 옆으로 이동
}
if (i == N) break;
}
printf("%d", maxh);
return 0;
}
