코드그라운드 개구리 뛰기

1년전 쯤 풀었던 코드그라운드 개구리 뛰기 문제입니다. 지금도 코드그라운드 사이트가 있는지 모르겠습니다만 알고리즘을 공유하는 차원에서 포스팅합니다.

 

코드그라운드 사이트 특징

1. 내가 제출한 문제의 득점을 확인할 수 있다.

예를 들어 아래 코드의 경우에는 100점으로 통과하였지만 통과 전까지 20, 40 점의 득점을 거쳐서 완성된 코스이다.

어디에서 잘못되었는지는 알려주지 않지만 다시 코드를 검토해보면서 완벽을 만들어가는 재미가 있다.

2. 다른 사람들이 제출한 코드를 확인할 수 있다.

- 실력향상을 위해서라면 미리 보지 않는 것을 추천한다.

3. 정답을 맞히면 포인 트까 쌓여서 랭킹을 확인할 수 있다.

- 학교별 랭킹 순위가 제공된다.

 

*** 아래는 내가 최근에 풀었던 코드 그라운드 spsc예선 문제 중 하나이다. ***

- 실제 문제는 그림과 함께 더 상세히 설명되어 있다.

<문제>

일직선 상에 돌들이 놓여있고, 개구리가 처음에는 좌표0에 위치한 돌에 앉아 있다.

개구리는 점프를 통해서 돌들 사이를 이동해 마지막 돌까지 이동해야 한다.

개구리가 한번의 점프로 이동 가능한 최대 거리 k가 주어진다

한 번의 점프로 자신이 앉아 있던 돌에서 k이하의 거리에 위치한 돌들 중 하나로 이동 가능하다.

좌표 0에 위치한 개구리가 마지막 도라지 이동할 수 있다면 최소 점프 횟수는?

 

<제한시간>

java 수행시간 2초 이내

 

<입력>

첫째줄) 돌의 개수

둘째 줄) 돌의 좌표(공백을 사이에 두고 입력)

셋째 줄) 최대 점프

 

<출력>

최소 점프 횟수 구하기

만약 개구리가 마지막 돌로 이동하는 것이 불가능하면 -1 출력하기

예를 들어,

<입력>

6

1 3 4 6 10 13

5

이렇게 입력을 했을 때 아래와 같이 출력이 되면 된다.

<출력>

4

package test1_frog;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
 
class Frog {
    static int Answer;
 
    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 myLoc = 0;
            int Num = sc.nextInt();
            int[] locList = new int[Num + 1];
            locList[0] = 0;
            for (int i = 1; i <= Num; i++) {
                locList[i] = sc.nextInt();
            }
            int maxJump = sc.nextInt();
            // ***변수 입력 및 초기화 끝***
 
            
            for (int i = 1; i < locList.length; i++) {
                // 점프가 불가능한 경우의 처리를 먼저 함으로써 오류 방지.
                if (locList[i] - locList[i - 1] > maxJump) {
                    Answer = -1;
                    break;
 
                } else {
 
                    // (1) 최대점프거리에 딱맞는 돌이 있을 경우의 처리
                    if (locList[i] - myLoc == maxJump) {
                        myLoc = locList[i];
                        Answer++;
                        continue;
 
                        // (2) maxJump(점프범위)를 최소한으로 넘겨서 이동할 수 없는 돌의 위치를 찾는다. 
 //그 후 바로 앞의 인덱스, 즉 점프범위를 넘겨서 못가는 돌의
 //앞에 위치한 돌이라면 내가 최대한으로 이동할 수 있는 돌이 된다. 
 //바로 그곳으로 나의 위치를 이동시켜준다. 
                    } else if (locList[i] - myLoc > maxJump) {
                        myLoc = locList[i - 1];
                        i--;
                        Answer++;
 
                        // (3) 마지막 돌은 무조건 도착
                    } else if (locList[i] == locList[Num]) {
                        Answer++;
                    }
                }
            }
 
            System.out.println("Case #" + (test_case + 1));
            System.out.println(Answer);
        }
    }
}