#include<stdio.h>
int main() {

int N,i,j,k,temp_a,temp_b,temp_Max=0,Max=0;
int arr[111111][2]={0,};

scanf("%d", &N);
for(i=0; i<N; i++) scanf("%d %d", &arr[i][0], &arr[i][1]);

for(i=0; i<N; i++) {
for(j=i+1; j<N; j++) {

if(arr[i][0] > arr[j][0]) {

temp_a = arr[j][0];
temp_b = arr[j][1];
arr[j][0] = arr[i][0];
arr[j][1] = arr[i][1];
arr[i][0] = temp_a;
arr[i][1] = temp_b;

}

else if(arr[i][0]==arr[j][0]) {
if(arr[i][1] > arr[j][1]) {

temp_b = arr[i][1];
arr[i][1] = arr[j][1];
arr[j][1] = temp_b;

}
}
}
}
for(i=0; i<N; i++) {
temp_a = arr[i][0];
temp_b = arr[i][1];
temp_Max++;
j=i;
while(1) {
if(arr[j][0] >= temp_b) {

temp_a = arr[j][0];
temp_b = arr[j][1];
temp_Max++;
if(Max <= temp_Max) Max=temp_Max;

}

else j++;

if(j==N) {
temp_Max=0;
break;
}

}
}
printf("%d\n", Max);
return 0;
}
#include<stdio.h>
int main() {

int N,i,j,k,temp_a,temp_b,temp_Max=0,Max=0;
int arr[111111][2]={0,};

scanf("%d", &N);
for(i=0; i<N; i++) scanf("%d %d", &arr[i][0], &arr[i][1]);

for(i=0; i<N; i++) {
for(j=i+1; j<N; j++) {

if(arr[i][0] > arr[j][0]) {

temp_a = arr[j][0];
temp_b = arr[j][1];
arr[j][0] = arr[i][0];
arr[j][1] = arr[i][1];
arr[i][0] = temp_a;
arr[i][1] = temp_b;

}

else if(arr[i][0]==arr[j][0]) {
if(arr[i][1] > arr[j][1]) {

temp_b = arr[i][1];
arr[i][1] = arr[j][1];
arr[j][1] = temp_b;

}
}
}
}
for(i=0; i<N; i++) {
temp_a = arr[i][0];
temp_b = arr[i][1];
temp_Max++;
j=i;
while(1) {
if(arr[j][0] >= temp_b) {

temp_a = arr[j][0];
temp_b = arr[j][1];
temp_Max++;
if(Max <= temp_Max) Max=temp_Max;

}

else j++;

if(j==N) {
temp_Max=0;
break;
}

}
}
printf("%d\n", Max);
return 0;
}

그냥 나이브 하게 구현했는데 시간초과가 뜨네요. 시간초과 안나게 하기 위해서 어떤 알고리즘을 써야 하는 걸까요?

mrcamel   2년 전

정렬하면서 시간이 오래걸리네요

std:sort 써보세요

댓글을 작성하려면 로그인해야 합니다.