시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 864 | 316 | 259 | 40.852% |
창영이는 버스에서 내린 뒤 회사로 걸어가고 있다. 창영이가 걸어가는 길은 대부분 회색 보도블럭으로 포장되어 있는데, 가끔씩 빨간 보도블럭이 놓여있을 때가 있다. 창영이는 어린 시절 빨간 보도블럭만 골라서 밟고 다니던 기억이 떠올랐다. 창영이는 중간에 회색 보도블럭을 밟지 않고 빨간 보도블럭만 최대한 많이 밟고 이동해 보기로 했다.
이제부터 편의상 빨간 보도블럭을 모두 블럭이라고 부르자.
창영이의 앞에는 총 N개의 블럭이 직선 상에 놓여 있다. 각 블럭을 창영이와 가까운 순서대로 1, 2, ... N번 블럭이라고 하자. i번 블럭과 i+1번 블럭은 길이 Li만큼 떨어져 있다. 창영이는 한 걸음에 길이 K만큼 이동할 수 있는데, 임의의 i번 블럭에서 i+1번 블럭으로 이동하려면 Li ≤ K를 만족해야 한다. 단, 창영이는 최대 한 번 점프를 해서 거리에 상관 없이 i번 블럭에서 i+1번 블럭으로 이동할 수 있다. 만약 창영이가 다음 블럭을 밟을 수 없다면 창영이의 기록은 거기서 끝나게 된다. 뒤로 돌아가서 밟았던 블럭을 다시 밟는 경우는 없다고 하자.
창영이는 최적의 시작점을 찾아서 빨간 보도블럭 연속 밟기의 최고 기록을 세우려고 한다. 창영이가 최대 몇 개의 블럭을 연속적으로 밟을 수 있을지 알아보자.
첫째 줄에 빨간 보도블럭의 개수 N, 창영이의 보폭 K가 주어진다.
둘째 줄에 각 빨간 보도블럭 사이의 거리 Li가 N-1개 주어진다.
시작점을 임의로 설정하고 점프를 최대 한 번 할 수 있을 때, 창영이가 연속해서 밟을 수 있는 빨간 보도블럭의 최대 개수를 출력한다.
7 3 2 3 1 5 3 5
6
7 3 2 3 1 5 3 3
7
5 3 4 4 1 1
4