[Code Ground][SCPC 예선 - 개구리 뛰기]

문제

https://www.codeground.org/practice

문제해결

처음 고안한 방법으로는 다이나믹 프로그래밍으로 1~N까지 그때그때마다 최소로 점프할 수 있는 횟수를 업데이트해줘서 마지막 목적지까지 구해주는 방식으로 했으나 시간초과로 80점을 받았다... O(N)으로 풀어야 했기에 한번에 반복문만을 사용해야만 한다.

다음위치 <= 현재 위치에서 최대로 점프가능한 위치 < 다다음 위치을 찾아서 가면 O(N)으로도 충분히 가능하다.

처음 생각은 점프을 무조건 많이 뛰다보면 목적지에 도달 못 할 수도 있겠구나 싶었는데 그게 아니었다.

무조건 멀리가는것이 맞다!!

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int N,K;
int bridge[1000001];
int main(int argc, char** argv)
{
    int T, test_case;
    cin >> T;
    for(test_case = 0; test_case  < T; test_case++)
    {
        cin >> N;
        for(int i = 1;i<=N;i++){
            cin >> bridge[i];
        }
        cin >> K;
        int temp = 0; // 현재자리수+K를 저장 즉 최대로 건넜을때 위치임
        int location = 0; //위치, 즉 최대로 건널 수 있는 돌다리의 위치를 저장한것(현재 와있는 위치라고 생각하면됨) 
        int sol = 0; // 점프한 횟수
        for(int i = 1;i<=N;i++){
            temp = location+K; //최대로 건넜을 떄 위치
            if(temp>=bridge[i]){ //만약 돌다리 위치가 최대로 건넜을때의 위치보다 작거나 같을떄
                if(i == N){ // 만약 마지막 위치라면 sol을 +1해주고 종료
                    sol++;
                    break;
                }
                if(temp<bridge[i+1]){ //만약 다다음 돌다리보다 작으면 최대로 건너는 것이므로 현재 위치를 수정하고 돌다리를 점프하므로 sol +1
                    location = bridge[i];
                    sol++;
                }
            }
            else{ //최대로 건너는 위치보다 돌다리가 멀리 있으면 앞으로 못가므로 -1해준다.
                sol = -1;
                break;
            }
        }
        cout << "Case #" << test_case+1 << endl;
        cout << sol<<"\n";
    }
 
    return 0;//Your program should return 0 on normal termination.
}