문제
일직선 상에 돌들이 놓여있고, 개구리가 처음에는 ‘좌표 0’에 위치한 돌 위에 앉아 있다. ‘좌표 0’에는 돌이 항상 놓여 있고, 모든 돌들은 정수 좌표에 놓여 있다. (그림 1)
개구리는 점프를 통해서 돌들 사이를 이동해서 마지막 돌까지 이동해야 한다. 이 때, 개구리가 한번의 점프로 이동 가능한 최대 거리 K 가 주어진다. 개구리는 한번의 점프로 자신이 앉아 있던 돌에서 K 이하의 거리에 위치한 돌들 중 하나의 돌로 이동 할 수 있다. 여기서 문제는, ‘좌표 0’에 위치한 개구리가 마지막 돌까지 이동할 수 있다면, 마지막 돌까지 이동하기 위한 최소 점프 횟수를 계산하는 것이다.
예를 들어서, 위의 “그림1”의 예에서 보면, 한번의 점프로 이동 가능한 최대 거리가 K=4 로 주어질 때, 아래 “그림2”에서와 같이 5회의 점프로 마지막 돌로 이동할 수 있고, 이것이 최소의 점프 횟수이다.
또한 위의 예에서, K=2 로 주어진다면 개구리는 마지막 돌로 이동할 수가 없다. 왜냐하면, 개구리가 ‘좌표 2’의 돌로 이동한 후 ‘좌표 5’이상의 돌로는 이동할 수 없기 때문이다.
입력
입력 파일에는 여러 개의 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에는 테스트 케이스 개수를 나타내는 자연수 T가 주어지고, 이후 차례로 T개의 테스트 케이스가 주어진다. ( 1≤T≤5 ) 각각의 테스트 케이스 첫 번째 줄에는 ‘좌표 0’에 놓인 돌을 제외한 나머지 돌들의 개수 N 이 주어진다. ( 1≤N≤1,000,000 ) 두 번째 줄에는 돌들이 놓인 좌표를 나타내는 N 개의 정수 ai들이 빈칸(공백)을 사이에 두고 주어진다. (1≤ai≤109 ) 여기서, 주어진 좌표들은 증가하는 순서로 주어지고 모두 다르다. 세 번째 줄에는 개구리가 한 번의 점프로 이동 가능한 최대 거리 K 가 주어진다. ( 1≤K≤109 )
출력
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며, 각 테스트 케이스마다 첫 줄에 “Case #T”를 출력하여야 한다. 이때 T는 테스트 케이스의 번호이다. 그 다음 줄에는 개구리가 마지막 돌로 이동할 수 있는 최소 점프 횟수를 출력한다. 만약, 개구리가 마지막 돌로 이동하는 것이 불가능한 경우에는 “-1”을 출력한다.
import java.util.Scanner;
class Solution {
static int Answer;
static int idx;
static boolean solve(int[] arr, int k, int loc) {
idx = 0;
if(loc == arr.length-1) return false;
for(int i=loc+1; i<arr.length; i++) {
if(arr[loc]+k >= arr[i]) {
idx = i;
} else break;
}
if(idx!=0) {
Answer++;
return true;
}
else {
Answer = -1;
return false;
}
}
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int test_case = 0; test_case < T; test_case++) {
Answer = 0;
int loc = 0; //현재 위치
// 돌의 개수
int N = sc.nextInt();
int[] a = new int[N+1];
a[0] = 0;
// 0을 제외한 돌의 위치
for(int i=1; i<=N; i++) {
a[i] = sc.nextInt();
}
// 한번에 이동가능한 최대 거리
int K = sc.nextInt();
boolean flag = true;
solve(a, K, loc);
while(flag) {
flag = solve(a, K, idx);
}
System.out.println("Case #"+(test_case+1));
System.out.println(Answer);
}
}
}
코드 설명
우선 배열을 현재 위치인 0을 포함해서 N+1크기로 생성한 후 각 위치를 저장한다.
현재 위치를 기준으로 K를 더한 값보다 다음 위치가 같거나 작다면 그 index를 임시로 저장하고 넘어간다. (그 다음 위치도 한 번에 이동할 수 있을 수 있기 때문에 바로 움직이지 않는다.)
다음 solve 함수를 호출할 때는 변경된 현재 위치와 함께 호출한다.
그 다음 위치가 최대 거리 더한 값보다 클 때 임시로 저장한 값이 없다면 마지막 돌까지 이동이 불가능 하므로 -1을 저장하고 반복문을 빠져나간다.