글 읽기 - 3463 떨어지는 개미 푸는 방식이 어떻게 되나요??

mts90 5년 전 0

개미가 충돌하면 그냥 지나치는 것 이라고 가정하는 문제라는 건 알겠는데

ID가 양수면 시간은 L-position

ID가 음수면 시간은 position 이잖아요????

그런데 이렇게 해서 쭉 결과를 냈으면

어떤놈들이 충돌해서 바뀐건지를 알아야 하는데 이 부분이 도저히 모르겠어요

아래 코드는 시간초과난 코드인데요 배열을 2개 만들어서 오른쪽으로 가는 경우 왼쪽으로 가는 경우 나눴습니다.

#include <stdio.h>

int lensub[5000001];
int lenplus[5000001];
int order[100000];

int main ()
{
	int t;
	int n,l,k;
	int i,j=0,n1,a=0,cpl;
	int antid , antposition;
	int s,p,tmp=0;

	scanf("%d",&t);

	while (t)
	{
		scanf("%d %d %d",&n,&l,&k);
		i=0;j=0;tmp=0;a=0;
		n1=n;
		cpl=l;

		while (n1)
		{   // 배열을 100만으로 하는 이유는 3번째 방에 +3이 있고, 4번째 방에 -5가 있다고 가정하면
			// 얘네는 t=0.5일때 만나는 것이고 배열에 표현하는 것이 애매해진다. 하지만 배열을 2배로 키운다면 절대 t=0.5 일때 만날 수가 없다. 

			// len 배열에 해당하는 id의 시작지점을 지정해준다.
			// 만나는 경우를 생각해줘야 하므로 id가 양, 음수 일때 각자 해당 배열에 입력한다.
			// position은 인덱스로 ID는 요소로 가정한다.
			scanf("%d %d",&antposition,&antid);

			if (antid<0)
			{s=2*antposition; lensub[s]=antid;}
			else
			{p=2*antposition; lenplus[p]=antid;}
			n1--;
		}



		/*for (i=0;i<=l;i++)
		printf("%3d",lenplus[i]);
		puts("");
		for (i=0;i<=l;i++)
		printf("%3d",lensub[i]);
		puts("");
		puts("");*/

		while (1)
		{
			// 개미가 충돌 할 때 위치를 바꿔줘야한다.
			// 한 번 반복 때 마다 id가 양수이면 오른쪽으로
			// id가 음수이면 왼쪽으로
			// p,s를 0부터 시작하면 시간복잡도가 장난 아니니까 0이 아닌 부분만 체크한다.
			// 해당 인덱스의 요소가 0이 아니면 plus는 오른쪽으로 sub는 왼쪽으로 보낸다.

			for(i=1;i<cpl;i++)
			{
				// 동시에 다발적로 만날수도 있으니 반복문으로 확인한다.
				// 두 개의 요소가 0이 아닌데 두 개의 인덱스가 같다면 만났다는 의미이다.
				// 만난 두 개 ID의 배열을 바꿔준다.
				if (lenplus[i]!=0 && lensub[i]!=0)
				{ tmp=lensub[i]; lensub[i]=lenplus[i]; lenplus[i]=tmp; }
			} 
			a=0;
			for(;i>0;i--)
			{
				if (lenplus[i]!=0)
				{ lenplus[i+1]=lenplus[i]; lenplus[i]=0;} 

				if(lensub[a]!=0)
				{ lensub[a-1]=lensub[a]; lensub[a]=0;}
				a++;
			}



			/*for (a=0;a<=cpl;a++)
			{
			printf("%3d",lenplus[a]);
			}
			puts("");

			for (a=0;a<=cpl;a++)
			{
			printf("%3d",lensub[a]);
			}
			puts("");
			puts("");*/





			if (lenplus[cpl]!=0 && lensub[0]!=0)
			{
				if(lenplus[cpl]<lensub[0])
				{order[j]=lenplus[cpl];j++;
				if (j-1==k-1) 
					break;
				order[j]=lensub[0];j++; lenplus[cpl]=0;lensub[0]=0; }
				else
				{order[j]=lensub[0];j++;
				if (j-1==k-1) 
					break;
				order[j]=lenplus[cpl];j++; lenplus[cpl]=0;lensub[0]=0; }
			}

			else if (lenplus[cpl]!=0 && lensub[0]==0)
			{order[j]=lenplus[cpl];j++;lenplus[cpl]=0;}

			else if (lenplus[cpl]==0 && lensub[0]!=0)
			{order[j]=lensub[0];j++;lensub[0]=0;}

			//printf("%d \n",order[j-1]);

			//차례를 저장해둔 배열의 (인덱스-1)과 k가 같으면 k번째 값이 들어왔다는 뜻이고 반복문을 끝낸다.
			if (j-1==k-1) 
				break;			
		}
		printf("%d\n",order[k-1]);
		t--;

		for (i=0;i<=cpl;i++)  //배열을 초기화
		{
			lensub[i]=0;
			lenplus[i]=0;
			order[i]=0;
		}
	}

	return 0;

}

BaaaaaaaaaaarkingDog 5년 전 2

코드를 제대로 읽어보지는 않았지만, 개미문제를 푸는데 쓰이는 또 다른 중요한 성질중 하나는 "번호간의 순서는 절대 바뀌지 않는다."입니다.

예를 들어 번호 5 9 2 14 순으로 직선위에 있었다 치면, 아무리 시간이 흘러도 개미들의 위치는 달라질지언정 5 9 2 14라는 순서는 절대 바뀌지 않아요. 그걸 유념하고 다시 문제를 보면 중간중간 발생하는 번호의 교환을 전부 기억하는 대신 왼쪽으로 떨어진 개미의 수와 오른쪽으로 떨어진 개미의 수만 알면 된다는 점을 알 수 있을 거에요.

atomzeno 5년 전 1

진짜 그냥 윗 분 말대로 하시면 될 듯 ㅎㅎ

좀 보충을 하면, 4(->), 5(->), -1(<-), -3(<-), -2(<-), 6(->)이 충돌하고 그 결과가 4(<-), 5(<-), 1(<-), -3(->), -2(->), 6(->) 이 된다는 사실을 관찰한 뒤에

각 화살표를 대응시키는 것(4->3, 5->2, 6->6, -1->4, -3->5, -2->1)을 생각하시면 O(NlogN)만에 알아낼 수 있을듯 합니다(~~맞겠지~~)

mts90 5년 전 1

역시 고수님들은 달라도 많이 다르네요!!!

완전 감사합니다!!!!!!!!!!!!!!

한방에 퐉 이해가 됐어요

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

문제

문제

출처

ICPC

3463 떨어지는 개미 푸는 방식이 어떻게 되나요??

mts90 5년 전 0

BaaaaaaaaaaarkingDog 5년 전 2

atomzeno 5년 전 1

mts90 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말