[BOJ/백준] 2846 - 오르막길 (Python)

문제

문제링크

오르막길의 크기는 부분 수열의 첫번째 숫자와 마지막 숫자의 차이이다.

길이가 n인 수열에서 가장 큰 오르막길의 크기를 구하라.

 

풀이

바로 앞 뒤의 값을 비교하면서 뒤의 값이 더 크다면 오르막이다. (동일한 경우는 오르막길 아님)

이때 뒤의 값으로 up값을 갱신해주고 계속 진행한다.

그러다 뒤의 값(roads[i])이 더 크거나 앞의 값과 같아지는 경우, 이 길은 내리막 혹은 평지가 된다.

이 경우에 현재 상태에서의 up값과 down값의 차이를 리스트에 추가하고 up, down값을 현재 값(roads[i])으로 갱신한 다음 앞의 과정을 반복한다.

for문이 종료되면 리스트에는 수열에서의 모든 오르막길의 크기가 담겨있다.

문제에서는 가장 큰 오르막길의 크기를 원하므로 max(리스트)을 이용하면 된다.

 

코드

n=int(input())
roads=list(map(int, input().split()))

height=[0]
down, up=roads[0], roads[0]
for i in range(1,len(roads)):
    if roads[i]<=roads[i-1]:
        height.append(up-down)
        down, up=roads[i], roads[i]
    elif roads[i]>roads[i-1]:
        up=roads[i]

height.append(up-down)
print(max(height))