1R/2016 07 08 - Revision history

Maintenance script: Repair pages found by live-compare batch 0001

2026-03-26T14:46:15Z

Repair pages found by live-compare batch 0001

← Older revision		Revision as of 14:46, 26 March 2026
Line 31:		Line 31:
	for(int i=1;i<=n;i++){		for(int i=1;i<=n;i++){
	res.push_back(-1);		res.push_back(-1);
	for(int j=i-1;j>=0 && dol[i]-dol[j]<=k;j--)		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;		if(res[i]==-1 \|\| res[i]>res[j]+1) res[i]=res[j]+1;
	}		}

	std::cout<<"Case #"<<t<<std::endl<<res[n]<<std::endl;		std::cout<<"Case #"<<t<<std::endl<<res[n]<<std::endl;
	}		}
	return 0;		return 0;
Line 63:		Line 63:
	for(;i<=n;i++){		for(;i<=n;i++){
	res.push_back(-1);		res.push_back(-1);
	for(;dol[i]-dol[j]>k;j++);		for(;dol[i]-dol[j]>k;j++);
	if(i==j) break;		if(i==j) break;
	res[i]=res[j]+1;		res[i]=res[j]+1;
	}		}
	if(i==n+1) std::cout<<"Case #"<<t<<std::endl<<res[n]<<std::endl;		if(i==n+1) std::cout<<"Case #"<<t<<std::endl<<res[n]<<std::endl;
	else std::cout<<"Case #"<<t<<std::endl<<-1<<std::endl;		else std::cout<<"Case #"<<t<<std::endl<<-1<<std::endl;
	}		}
Line 111:		Line 111:
	break;		break;
	}		}
	now = vec[index];		now = vec[index];
	if (now + k < vec[index + 1]){		if (now + k < vec[index + 1]){
	ans = -1;		ans = -1;
	break;		break;
Line 120:		Line 120:
	break;		break;
	}		}
	if (vec[index] + k < vec[i]){		if (vec[index] + k < vec[i]){
	break;		break;
	}		}
Line 147:		Line 147:
	* 마지막 돌에 도착할때까지 위를 반복하여 몇번 점프를 하는지 계산한다.		* 마지막 돌에 도착할때까지 위를 반복하여 몇번 점프를 하는지 계산한다.
	* DP문제일까..?		* DP문제일까..?

2016-07-08T15:07:29Z

@@ Line 72: / Line 72: @@
       return 0;
+  }
+== 15이원준 ==
 = 아이디어 =
 == 박인서 ==
@@ Line 79: / Line 141: @@
 * 각각의 돌마다 거리를 비교하면서 하면 될 줄 알았으나..'''시간초과가 남'''(N크기 최대 백만, 시간복잡도-O(N^2))
 * 따라서 거리 비교를 최소화 하려고 변수를 하나 도입, 뒤에서 쫓아가면서 거리를 확인(시간복잡도-O(N))

2016-07-08T07:35:23Z

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

2016-07-08T07:34:44Z

← Older revision		Revision as of 07:34, 8 July 2016
Line 7:		Line 7:

	= 코드 =		= 코드 =
			== 박인서 ==
			=== 시간 초과 코드 ===
			#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;
			}

	= 아이디어 =		= 아이디어 =

2016-07-08T07:24:50Z

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

2016-07-08T07:23:40Z

← Older revision		Revision as of 07:23, 8 July 2016
Line 13:		Line 13:
	* 업 시퀀스 문제라 봐야될 것 같다.		* 업 시퀀스 문제라 봐야될 것 같다.
	* 각각의 돌마다 거리를 비교하면서 하면 될 줄 알았으나.. '''시간초과가 남'''		* 각각의 돌마다 거리를 비교하면서 하면 될 줄 알았으나.. '''시간초과가 남'''
	* 따라서 거리 비교를 최소화 하려고 ~~be 변수~~ 도입, 뒤에서 쫓아가면서 거리를 확인		* 따라서 거리 비교를 최소화 하려고 변수를 하나 도입, 뒤에서 쫓아가면서 거리를 확인

2016-07-08T07:22:30Z

← Older revision		Revision as of 07:22, 8 July 2016
Line 9:		Line 9:

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

2016-07-08T06:56:21Z

{CREATE}

New page

__TOC__

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

= 참가자 =

= 코드 =

= 아이디어 =