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;
}

15이원준

// 아래 기본 제공된 코드를 수정 또는 삭제하고 본인이 코드를 사용하셔도 됩니다.
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char** argv) {
	/* 아래 freopen 함수는 input.txt 를 read only 형식으로 연 후,
	앞으로 표준 입력(키보드) 대신 input.txt 파일로 부터 읽어오겠다는 의미의 코드입니다.
	만약 본인의 PC 에서 테스트 할 때는, 입력값을 input.txt에 저장한 후 freopen 함수를 사용하면,
	그 아래에서 scanf 함수 또는 cin을 사용하여 표준입력 대신 input.txt 파일로 부터 입력값을 읽어 올 수 있습니다.
	또한, 본인 PC에서 freopen 함수를 사용하지 않고 표준입력을 사용하여 테스트하셔도 무방합니다.
	단, Codeground 시스템에서 "제출하기" 할 때에는 반드시 freopen 함수를 지우거나 주석(//) 처리 하셔야 합니다. */
	//freopen("input.txt", "r", stdin);

	setbuf(stdout, NULL);

	int TC;
	int test_case;

	scanf("%d", &TC);	// cin 사용 가능
	for (test_case = 1; test_case <= TC; test_case++) {
		// 이 부분에서 알고리즘 프로그램을 작성하십시오.
		vector<int> vec;
		int n, k, temp, now, index, ans = 0, i;
		cin >> n;
		vec.push_back(0);
		for (i = 0; i < n; i++){
			scanf("%d", &temp);
			vec.push_back(temp);
		}
		cin >> k;
		n++;
		for (index = 0; index < n;){
			if (index == n - 1){
				break;
			}
			now = vec[index];
			if (now + k < vec[index + 1]){
				ans = -1;
				break;
			}
			for (i = index + 1; i <= n; i++){
				if (i == n){
					break;
				}
				if (vec[index] + k < vec[i]){
					break;
				}
			}
			index = i - 1;
			ans++;
		}

		// 이 부분에서 정답을 출력하십시오.
		printf("Case #%d\n", test_case);	// cout 사용 가능
		cout << ans << endl;
	}

	return 0;	// 정상종료 시 반드시 0을 리턴해야 합니다.
}

아이디어

박인서

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

15이원준

• 현 블록에서 다음 블록으로 넘어갈수 있다면 최소한 -1은 아니라는 것이다.
• 다음 블록보다 어느 블록까지 더 갈수 있는지만 돌려본다.
• 위의 과정이 한번의 점프이다.
• 마지막 돌에 도착할때까지 위를 반복하여 몇번 점프를 하는지 계산한다.
• DP문제일까..?