글 읽기 - 8984번...

skan1543 10년 전 0

제가 생각한 솔루션은..

가장 출발점이 될수있는 선부터 탐색을 시작하여..

이 선을 타고 올라갔을때, 타고 내려왔을때.. 각각의 만나서 이어지는 선들을 전부 찾은뒤.. 값을 갱신해주는 형태로 풀었는데요..ㅠㅠ

피곤해서 설명이 횡설수설이네요..

찾을건 이진탐색으로 찾아주고.. 나름 시간복잡도를 O(N(lgN+x))까지 줄였는데 흑흑 ㅠㅠ

어떻게 해주어야 할까요...ㅎ

#include<stdio.h>
#include<math.h>
#include<algorithm>

using namespace std;

struct LINE {
	int x,y;
	__int64 down,up;

}; LINE line[100001]={0,};   // x하고 y만 따로 해서 정렬하자.
struct tLINE {
	int x,y;
	int index;

}; tLINE tline[100001]={0,};   // x하고 y만 따로 해서 정렬하자.
int x[100001],y[100001],n;

int structCompare(const void *a, const void *b)
{
     struct LINE *tempA = (struct LINE *)a;//(1)
     struct LINE *tempB = (struct LINE *)b;//(2)
     if(tempA->x!=tempB->x) return tempA->x>tempB->x;
	 else return tempA->y>tempB->y;
}

int structCompare2(const void *a, const void *b)
{
     struct tLINE *tempA = (struct tLINE *)a;//(1)
     struct tLINE *tempB = (struct tLINE *)b;//(2)
     if(tempA->y!=tempB->y) return tempA->y>tempB->y;
	 else return tempA->x>tempB->x;
}

int findindex(int weight)
{
	int left=0;
	int right=n-1;
	while(left<=right)
	{
		int mid=(left+right)/2;

		if(tline[mid].y>weight)
			right=mid-1;
		else if(tline[mid].y<weight)
			left=mid+1;

		else return mid;
	}
	return 0;
}

int main( )
{
	FILE *in=fopen("input.txt","r");
	int	l,i,j;
	
	fscanf(in,"%d %d",&n,&l);
	
	for(i=0;i<n;i++)
	{
		fscanf(in,"%d %d",&line[i].x,&line[i].y);
		line[i].down=abs(line[i].x-line[i].y)+l;
		line[i].up=abs(line[i].x-line[i].y)+l;
	}

	qsort(line,n,sizeof(LINE),structCompare);

	for(i=0;i<n;i++){
		tline[i].x=line[i].x;
		tline[i].y=line[i].y;
		tline[i].index=i;
	}

	qsort(tline,n,sizeof(tLINE),structCompare2);

	for(i=0;i<n;i++)
	{
		int idx=findindex(line[i].y);	

		for(j=idx;j>=0;j--)
			if(tline[j].x<=line[i].x || tline[j].y!=line[i].y) break;
		idx=j+1;

		for(j=idx;j<n;j++) if(tline[j].y!=line[i].y) break;
		int idx2=j-1;
		

		for(j=idx;j<=idx2;j++)
		{
			if(tline[j].x>line[i].x && line[tline[j].index].up < line[i].down+abs(line[tline[j].index].x-line[tline[j].index].y)+l)
				line[tline[j].index].up=line[i].down+abs(line[tline[j].index].x-line[tline[j].index].y)+l;
		}



		idx=i+1;
		for(j=idx;j<n;j++) if(line[j].x!=line[i].x) break;
		idx2=j-1;

		for(j=idx;j<=idx2;j++)
		{
			if(line[j].y>line[i].y && line[j].down < line[i].up+abs(line[j].x-line[j].y)+l)
				line[j].down=line[i].up+abs(line[j].x-line[j].y)+l;
		}
	}
	
	__int64 max=0;

	for(i=0;i<n;i++)
	{
		if(line[i].up>max) max=line[i].up;
		if(line[i].down>max) max=line[i].down;
	}

	printf("%I64d\n",max);
	return 0;
}

arine 10년 전 2

x, y가 t, d인 것 같은데 범위가 10^8까지 입니다. 시간 복잡도가 O(n(lg n+x))라 하셨으니 약 10^13까지도 돈다는 것인데 이러면 시간초과가 날 수 밖에 없겠죠. (시간제한이 1~2초일 때 보통 10^8정도까지 안전하다고 봅니다.)

이 문제를 풀기 위해 생각해야 하는 것은, n개의 막대기를 왼쪽부터 1,2,3,...,n번 막대기라 했을 때, k번째 막대를 끝으로 해서 만들 수 있는 지그재그 선의 최대 길이를 이미 알고 있다고 가정해봅시다. 그렇다면 k+1,...,n번째 막대에 대해서 이미 알고있는 값을 이용해 최대 길이를 구할 수 있지 않을까요?

여기까지 생각하셨다면 이 문제를 해결하기 위해 써야 하는 몇 가지 트릭이 더 있는데, 모바일로 꾹꾹 눌러적으려니 힘이 드네요...^^;; 마침 이 문제는 제가 연습하면서 정리해 두었던 것이라 링크(http://arine.me/plog/boj8984/)를 남깁니다. 스포일러 수준으로 해법이 적혀 있으니 다 푸신 후나 정 해법이 떠오르지 않을 때 참고하시면 좋을 것 같아요.

skan1543 10년 전 0

감사합니다... 그냥 대강 질문을 올려봤는데.. 답변 달아주셔서 감사드리구요 ㅠㅠ

풀이가 문뜩 떠올라 코딩하고 있던 참이었습니다. ㅎㅎ

바보같이 좌표를 갖고 동적계획을 하면 되는것을.. k번째 선까지 사용한 최대 길이. 를 구하려 하니 TL이 나는거였네요 ㅠㅠ

감사합니당 (_ _)

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

문제

문제

출처

ICPC

8984번...

skan1543 10년 전 0

arine 10년 전 2

skan1543 10년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말