징검다리 건너기 (small)

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 돌에 값 A_i가 주어질 때, i에서 j로 이동하는 비용이 (j-i)*(1+|A_i-A_j|)이고 한 번에 K 이하만 쓸 수 있을 때 마지막 돌에 도달할 수 있는지 판정합니다.

문제

$N$ 개의 돌이 일렬로 나열되어 있다. $N$ 개의 돌에는 왼쪽부터 차례대로 수 $A_{1}, A_{2}, ..., A_{i}, ..., A_{N}$ 가 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.

항상 오른쪽으로만 이동할 수 있다.
$i$ 번째 돌에서 $j(i < j)$ 번째 돌로 이동할 때 $(j - i) \times (1 + |A_{i} - A_{j}|)$ 만큼 힘을 쓴다.
돌을 한 번 건너갈 때마다 쓸 수 있는 힘은 최대 $K$ 이다.

이때 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는지 구해보자.

첫 번째 줄에 돌의 개수 $N$ 과 쓸 수 있는 최대 힘 $K$ 가 공백으로 구분되어 주어진다.

두 번째 줄에는 $N$ 개의 돌의 수 $A_{i}$ 가 공백으로 구분되어 주어진다.

가장 오른쪽에 있는 돌로 이동할 수 있다면 YES를 출력한다. 이동하지 못하는 경우에는 NO를 출력한다.