Informatica Online Judge

  스노우 부츠(Silver) [2190 / 088E]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 8   Total Tried : 12


The Champion of this Problem (C++) : t1234 - 0ms / 640byte
My Best Submission (C++) : N/A

[USACO 2018(Dhruv Rohatgi & Brian Dean)]

Background

겨울이 와서, 존의 농장에 많은 눈이 내렸다.

존의 농가에서 젖소 축사까지에는 $N$개의 타일이 있는데,
편의상 각각의 타일 번호를 $1$, $2$, ..., $N$ 라고 할 때, 각 타일 위에는 $f_i$ 피트의 눈이 쌓여있다.

존의 악천후 대비 가방에는 $1$, $2$, ..., $N$ 까지의 번호가 붙여진 $B$ 쌍의 부츠가 있다.
어떤 부츠들은 다른 부츠들보다 좋고, 어떤 부츠들은 다른 부츠들보다 좋지 않다.
$i$번째 부츠를 이용하면 최대 $s_i$피트 깊이까지 버틸 수 있으며, 한 걸음 뛸 때마다 최대 $d_i$ 칸 앞으로 이동할 수 있다.

농부 존은 젖소들을 깨우기 위해, 1번 타일에서 움직이기 시작해서 N번 타일까지 이동해야한다.
1번 타일은 농부존의 농가 지붕 아래에 있고, N번 타일은 축사 지붕 아래에 있기 때문에 눈이 전혀 쌓여있지 않다.

하지만 안타깝게도, 가방에는 부츠들이 순서대로 쌓여있기 때문에 가장 위에 있는 부츠를 먼저 사용해야한다.
가장 위에 있는 부츠만 사용할 수 있고, 다른 부츠를 사용하기 위해서는 가장 위에 있는 부츠를 버려야 한다.

농부 존은 타일 위에서만 부츠를 갈아 신을 수 있는데, 그 타일 위에 f피트 만큼 눈이 쌓여있으면,
벗는 부츠와 새로 신는 부츠는 적어도 f피트 깊이 이상을 버틸 수 있어야 한다.
f피트 깊이 이상 버티지 못하는 부츠들은 버릴 수만 있다.

농부 존이 버려야 할 부츠를 최소화하기 위해,
젖소 축사까지 도착하기 위해서 필요한 부츠의 최소 개수를 알아내보자.
농부 존은 처음에 부츠를 신고 있지 않다.

Input

첫 번째 줄에 $N$과 $B$가 공백을 두고 입력된다.
두 번째 줄에는 $N$개의 정수가 공백을 두고 입력된다.; i번째 정수는 각 타일에 쌓여있는 눈의 깊이인 $f_i$를 의미한다. $f_1$과 $f_N$은 0이다.

그 다음 B개의 줄에는 $s_i$와 $d_i$가 공백을 두고 입력된다.

부츠들은 위에서 아래로 쌓여있는 순서이다. 따라서 1번 부츠는 가장 위에 있다.

[입력값의 정의역]
$2≤N, B≤250$
$0≤f_i≤1,000,000,000$
$f_1, f_N = 0$
$0≤s_i≤1,000,000,000$
$1≤d_i≤N-1$

Output

농부 존이 축사까지 도착하기 위해서 버려야하는 부츠의 최소 개수를 출력한다.

IO Example

입력
10 4
0 2 8 3 6 7 5 1 4 0
2 3
4 2
3 4
7 1

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]