5027 : 개구리1
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 7
•통과: 1
•만든사람: suakii
문제 설명
$1$번부터 $N$번까지 번호가 매겨진 $N$개의 돌이 일렬로 놓여 있습니다.
각 $i$번째 돌($1 \le i \le N$)의 높이는 $h_i$입니다.
처음에 개구리는 $1$번 돌 위에 있습니다.
개구리는 다음 행동을 반복하여 $N$번 돌까지 이동하려고 합니다.
• 돌 $i$에 있을 때, 돌 $i + 1$ 또는 돌 $i + 2$로 점프합니다.
• 이때 점프하여 착지한 돌을 $j$라고 하면, $|h_i - h_j|$만큼의 비용이 발생합니다.
개구리가 $N$번 돌에 도달하기까지 발생하는 비용 총합의 최솟값을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $2 \le N \le 10^5$
• $1 \le h_i \le 10^4$
• 입력되는 모든 값은 정수입니다.
각 $i$번째 돌($1 \le i \le N$)의 높이는 $h_i$입니다.
처음에 개구리는 $1$번 돌 위에 있습니다.
개구리는 다음 행동을 반복하여 $N$번 돌까지 이동하려고 합니다.
• 돌 $i$에 있을 때, 돌 $i + 1$ 또는 돌 $i + 2$로 점프합니다.
• 이때 점프하여 착지한 돌을 $j$라고 하면, $|h_i - h_j|$만큼의 비용이 발생합니다.
개구리가 $N$번 돌에 도달하기까지 발생하는 비용 총합의 최솟값을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $2 \le N \le 10^5$
• $1 \le h_i \le 10^4$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 돌의 개수 $N$이 주어집니다.
둘째 줄에 각 돌의 높이 $h_1, h_2, \dots, h_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 각 돌의 높이 $h_1, h_2, \dots, h_N$이 공백으로 구분되어 주어집니다.
출력 설명
개구리가 지불해야 하는 비용 총합의 최솟값을 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
10 30 40 20
출력 예시
COPY
복사되었습니다!
복사되었습니다!
30
도움
[예제 1 설명]
돌 1 $\rightarrow$ 2 $\rightarrow$ 4 순서로 점프하면, 비용 총합은 $|10 - 30| + |30 - 20| = 20 + 10 = 30$이 되어 최소가 됩니다.
돌 1 $\rightarrow$ 2 $\rightarrow$ 4 순서로 점프하면, 비용 총합은 $|10 - 30| + |30 - 20| = 20 + 10 = 30$이 되어 최소가 됩니다.