글 읽기 - 시간 초과 나왔습니다 능력자분들 도와주세요

(追記) (追記ここまで)

시간 초과 나왔습니다 능력자분들 도와주세요

14865번 - 곡선 자르기

mckingtori 7년 전 0

C언어로 작성한 No.14865 KOI 2017년 중등부 2번 문제인데요

일단 원리는 각각 봉우리들의 끝과 끝(X좌표)들을 탐색해서 저장하고

그 선분들의 위치관계로 포함관계를 알아내서 대입하는 것입니다.

채점해보니 시간 초과가 나오더군요.

웬만해서 새로운 자신만의 코드를 보여주는 것은 사절할게요.

제 코드에서 시간을 압축시키기 위해 뭘 더 할 수 있는지 팁이나 코드를 알려주시면 감사하겠습니다.

#include <stdio.h>
int N, Dot[1000000][2];
int forward(int a);
int backward(int b);
int max(int X, int Y)
{
 if(X>=Y) return X;
 return Y;
}
int min(int A, int B)
{
 if(B>=A) return A;
 return B;
}
int main()
{
 int i, j, k=0, Needend=0, NeedSave = 0;
 scanf("%d", &N);
 int Line[N][2];
 for(i=0; i<N; i++)
 {
 scanf("%d %d", &Dot[i][0], &Dot[i][1]);
 }
 for(i=0; i<N; i++)
 {
 if(Dot[i][1]<0 && forward(i)>0 && backward(i)<0)
 {
 Needend = 1;
 Line[k][0] = Dot[i][0];
 } else if(Dot[i][1]<0 && forward(i)<0 && backward(i)>0)
 {
 if(Needend)
 {
 Needend = 0;
 Line[k][1] = Dot[i][0];
 k++;
 } else
 {
 NeedSave = 1;
 Line[0][1] = Dot[i][0];
 k++;
 }
 }
 }
 if(NeedSave)
 {
 Line[0][0] = Line[k][0];
 }
 int NUM_S = k, NUM_N=0;
 int Checklist[k];
 for(i=0; i<k; i++)
 {
 Checklist[i]=1;
 }
 for(i=0; i<k-1; i++)
 {
 for(j=i+1; j<k; j++)
 {
 if(min(Line[i][1],Line[i][0])>min(Line[j][1],Line[j][0]) && max(Line[i][1],Line[i][0])<max(Line[j][1],Line[j][0]))
 {
 NUM_S--;
 Checklist[j]=0;
 } else if(min(Line[i][1],Line[i][0])<min(Line[j][1],Line[j][0]) && max(Line[i][1],Line[i][0])>max(Line[j][1],Line[j][0]))
 {
 NUM_S--;
 Checklist[i]=0;
 }
 }
 }
 for(i=0; i<k; i++)
 {
 NUM_N += Checklist[i];
 }
 printf("%d %d", NUM_S, NUM_N);
 return 0;
}
int forward(int a)
{
 if(a == N-1) return Dot[0][1];
 return Dot[a+1][1];
}
int backward(int b)
{
 if(!b) return Dot[N-1][1];
 return Dot[b-1][1];
}

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC