[[TableOfContents]]

= 오늘의 문제 =
 * [https://www.codeground.org/practice/practiceProbView.do?probId=11|개구리 뛰기]

= 참가자 =

= 코드 =
== 박인서 ==
=== 시간 초과 코드 ===
{{{
#include <iostream>
#include <vector>

int main()
{
    int TC;
    std::cin>>TC;
    for(int t=1;t<=TC;t++){
        int n,k;
        std::vector<int> dol,res;
        std::cin>>n;
        dol.push_back(0);
        for(int i=0;i<n;i++){
            int tem=0;
            std::cin>>tem;
            dol.push_back(tem);
        }
        std::cin>>k;
        
        res.push_back(0);
        for(int i=1;i<=n;i++){
            res.push_back(-1);
            for(int j=i-1;j>=0 && dol[i]-dol[j]<=k;j--)
                if(res[i]==-1 || res[i]>res[j]+1) res[i]=res[j]+1;
        }
        
        std::cout<<"Case #"<<t<<std::endl<<res[n]<<std::endl;
    }
    return 0;
}
}}}
=== 통과 코드 ===
{{{
#include <iostream>
#include <vector>

int main()
{
    int TC;
    std::cin>>TC;
    for(int t=1;t<=TC;t++){
        int n,k;
        std::vector<int> dol,res;
        std::cin>>n;
        dol.push_back(0);
        for(int i=0;i<n;i++){
            int tem=0;
            std::cin>>tem;
            dol.push_back(tem);
        }
        std::cin>>k;
        
        res.push_back(0);
        int i=1,j=0;
        for(;i<=n;i++){
            res.push_back(-1);
            for(;dol[i]-dol[j]>k;j++);
            if(i==j) break;
            res[i]=res[j]+1;
        }
        if(i==n+1) std::cout<<"Case #"<<t<<std::endl<<res[n]<<std::endl;
        else std::cout<<"Case #"<<t<<std::endl<<-1<<std::endl;
    }
    return 0;
}
}}}

= 아이디어 =
== 박인서 ==
 * DP 문제이다.
 * 업 시퀀스 문제라 봐야될 것 같다.
 * 각각의 돌마다 거리를 비교하면서 하면 될 줄 알았으나..'''시간초과가 남'''(N크기 최대 백만, 시간복잡도-O(N^2))
 * 따라서 거리 비교를 최소화 하려고 변수를 하나 도입, 뒤에서 쫓아가면서 거리를 확인(시간복잡도-O(N))