3.1.1. 시간 초과 코드 ¶
#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;
}
3.1.2. 통과 코드 ¶
#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;
}
3.2. 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을 리턴해야 합니다.
}










