개구리 뛰기 (Frog Leaps)

> 문제 출처

https://www.codeground.org/practice/

11 SCPC_2015_Online Frog Leaps

 

> 문제 설명

N개(<1,000,000)의 돌의 좌표와 한번의 점프로 이동 가능한 최대 거리K가 주어졌을 때 마지막 좌표까지 이동하기 위한 최소 횟수를 계산하는 문제. 이동이 불가하다면 -1을 리턴해야한다.

 

> 접근 방법

K값이 좌표 이전에 주어진다면 좌표 입력수준에서 편하게 풀 수 있었는데 좌표입력 후 K값이 주어지는거라 입력 후 처리를 할 수 밖에 없었다.

 

일단 최근 입력된 돌의 좌표를 입력받는 pos, pos부터 새로 입력된 좌표까지의 거리를 계산한 dist벡터를 선언하였다. 또한 개구리가 끝까지 갈 수 있는지 판단하기 위해 dist값의 최대값을 구해두었다. (이웃한 돌 사이의 거리가 K보다 큰 곳이 하나라도 있다면 개구리는 끝까지 가지 못한다.)

 

이제 max_dist값이 K이하라면 최소 횟수를 구할 수 있다. 시작점부터 K거리 이내의 가장 먼 돌을 찾아가면 최소 횟수로 도착을 할 것이다. 따라서 dist값을 차례대로 누적하여 그 값이 K보다 커지면 Count를 늘려주고, 누적값을 초기화하여 다시 누적하는 방식으로 답을 구하였다.

 

> CODE

/*
# problem
https://www.codeground.org/practice/
11	SCPC 2015 Online	
Frog Leaps

#review
https://ssyoon.tistory.com/17
*/
#include <iostream>
#include <vector>

using namespace std;

int Answer;

int main(int argc, char** argv)
{  
	int T, test_case,N,K;
	scanf("%d",&T);
	for(test_case = 0; test_case  < T; test_case++)
	{
	    Answer = 0;        
        scanf("%d",&N);

        vector<int> dist;
	    int pos=0;
        int tmp;
        int max_dist=0;
        for(int i=0;i<N;i++){
            scanf("%d",&tmp);
            dist.push_back(tmp-pos);
            pos = tmp;
            max_dist = max(max_dist,dist.back());
        }
        scanf("%d",&K);
        if(max_dist > K) Answer=-1;
        else{
            int acc_dist=0; //accumulated distance
            auto i=dist.begin();
            while(i!=dist.end()){
                acc_dist+= *i;
                if(acc_dist > K){
                    Answer++;
                    acc_dist=0;
                }
                else i++;
            }
            if(acc_dist > 0) Answer++;//check if acc_dist is remain.
        }        

		cout << "Case #" << test_case+1 << endl;
		cout << Answer << endl;
	}

	return 0;//Your program should return 0 on normal termination.
}

---

https://github.com/dongha-yoon/ProgrammingStudy - frog_leaps.cpp