1931번 - 회의실 배정
#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() {
if(j==N) { temp_Max=0; break; } } } printf("%d\n", Max); return 0;}
그냥 나이브 하게 구현했는데 시간초과가 뜨네요. 시간초과 안나게 하기 위해서 어떤 알고리즘을 써야 하는 걸까요?
정렬하면서 시간이 오래걸리네요
std:sort 써보세요
https://www.acmicpc.net/wiki/stl/sort
댓글을 작성하려면 로그인해야 합니다.
qkrtjdrb9573 9년 전
#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;
}
그냥 나이브 하게 구현했는데 시간초과가 뜨네요. 시간초과 안나게 하기 위해서 어떤 알고리즘을 써야 하는 걸까요?