1R/2016 07 08

오늘의 문제

• 뛰기

코드

박인서

시간 초과 코드

#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))