[백준 알고리즘] 3163번 떨어지는 개미

문제

개미 N마리가 막대 위에 올라가 있다. 일부 개미는 왼쪽을 바라보고 있고, 나머지 개미는 오른쪽을 바라보고 있다. 모든 개미는 매우 작아서 크기가 없는 점으로 나타낼 수 있다. 시작 신호가 주어지면, 개미는 바라보고 있는 방향으로 행진을 시작한다. 모든 개미는 동일한 속도 초속 1mm로 이동한다. 두 개미가 한 점에서 충돌하는 경우가 발생할 수 있다. 이 경우에 두 개미는 행진하는 방향을 반대 방향으로 바꾸고, 행진을 계속하게 된다. 개미가 방향을 바꾸는데 걸리는 시간은 없다. 개미가 막대의 끝에 도착하는 경우에는, 막대에서 떨어지게 된다. 막대는 땅 위에 떠있다고 가정한다.

처음에 모든 개미의 위치는 서로 다르다. 즉, 두 개미가 막대 위의 한 점에 같이 있는 경우는 없다. 개미는 부호 있는 정수로 나타낼 수 있다. 이 정수를 개미의 ID라고 한다. 개미의 ID의 부호는 개미가 처음에 바라보고 있는 방향이다. -는 왼쪽을 바라보고 있는 것이고, +는 오른쪽을 바라보고 있는 것이다. 개미의 ID의 절대값은 1부터 109까지의 정수 중 하나이다. 또, 모든 개미의 ID의 절대값은 서로 다르다. 아래 그림에는 개미가 총 6마리가 있고, ID는 {+4, +5, -1, -3, -2, +6}이다. 각 개미의 초기 위치는 {5, 8, 19, 22, 24, 25}이며, 막대의 길이 L = 30이다. 화살표는 처음에 개미가 바라보고 있는 방향을 나타낸다. 왼쪽 끝의 좌표는 0이고, 오른쪽 끝의 좌표는 30이다. ID가 +6인 개미는 시간 t = 5일 때, 막대의 오른쪽 끝에 도착하며, t = 6에 막대에서 떨어지게 된다.

개미가 행진을 시작하기 전의 상태 (ID와 막대 상의 위치)가 주어진다. 두 개미가 동시에 막대의 양 끝에서 떨어지는 경우에는, ID가 작은 개미가 조금 더 먼저 떨어진다고 한다. 아래 그림은 이와 같은 경우를 나타낸 그림이다. 두 개미 {-1, +2}는 끝에 동시에 도착하게 된다. -1 < +2 이기 때문에, ID가 -1인 개미가 +2인 개미보다 조금 더 먼저 떨어지게 된다. 따라서, 아래 그림의 네 개미가 떨어지는 순서는 {-1, 2, 4, 3}이 된다.

양의 정수 1 ≤ k ≤ n이 주어졌을 때, k번째로 떨어지는 개미를 구하는 프로그램을 작성하시오.

입력과 출력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N, L, k가 주어진다. 다음 N개 줄에는 pi와 ai가 주어진다. ai는 개미의 ID이고, pi는 그 개미의 초기 위치이다. 항상 pi가 증가하는 순서로 (pi<pi+1) 주어진다. (1 ≤ pi ≤ L-1, 3 ≤ N ≤ 100,000, 10 ≤ L ≤ 5,000,000, 1 ≤ k ≤ N)

각 테스트 케이스마다, N마리 개미 중에서 k번째로 떨어지는 개미의 ID를 출력한다. 개미의 ID가 양수인 경우에 +를 출력하면 안된다.

풀이

맨날 분류 정해서 풀었는데 이번문제는 그냥 풀게됐다 

for문으로 모든 개미들을 초기위치에서 id값에 따라서 +1또는 -1로 행진시킨다 ID작은아이 먼저 떨어뜨릴려면 처음에 아이디를 sorting 해두면 될 것 같은데..

예제 입력을 보면 n=6 L=30 k=3이고 

5 4 

8 5 

19 -1 

22 -3 

24 -2 

25 6

에서 5mm 행진후에는 id=6인애가 추락한다 그리고 그때 id=-1 인애는 위치가 14일거고 id=5인애의 위치는 8+5 = 13일거다 그러면 그다음 행진할 때 동시에 행진한다고(지금까지 총 6mm행진) 치면 id=-1인애가 위치가 13로 가고 id=5인애는 위치가 14가 될거니까 충돌하지 않는

다 이때 id = 4 인애는 위치가 10이고 id = -3인애는 위치가 22-6=16 id=-2인애는 위치가 18이다

이후 행진을 3씩 더 하게되면 id = 4 인애는 5(원래위치)+5+3 = 13    id = -1 인애는  ..

헐 이때까지 너무 잘못풀었다 id에 따라 sorting을 했지 p는 id에 따라다니는애라서 충돌을 볼때...전부를 비교해줘야하는 문제가 생겼다

다시... 문제를 차근차근 생각해보면

모든 개미가 행진한 만큼을 나타내는 변수 x를 두고 x를 늘려가면서 DP?같은 느낌으로 풀면 풀릴거 같다....

x가 증가할때마다 id값에 따라 p[i]+=1; 이거나 p[i]-=1; 이다 이때 p[i] 중에서 같은게 있다는게 충돌을 했다는건데 처음부터 돌면서 비교하기엔 시간이 너무 오래걸려서 비효율적일거같은데..무튼 충돌하는 경우는 저경우고

p[i]==0 또는 p[i]==L 이되면 i번째 개미가 떨어진것이다 

각 id마다 가야하는 길 계산하면 

25 22 19 22 24 5

5빼면

20 17 14 17 19 0-> 맨마지막애가 도착한거

14빼면

17 6 0 3 6 0 -> 앞에서 세번째 애가 도착한거

3빼면

14 3 0 0 3 0 ->뒤에서 세번째 애가 도착일려면 id로 비교해줘야함

가야하는 길 부호랑 같이 보기위해 다시 해보면

+25 +22 -19 -22 -24 +5

여기서 개미 한마리를 떨어뜨리려면 +5만 가면되는 개미를 제일 먼저 갈수있게한다

5를 행진했다고 하면 +인곳에는 빼주고 -인곳에는 더한다

+20 +17 -14 -17 -24 0 -> 맨마지막 개미는 떨어진다 

이때 위치는

30-20= 10, 30-17=13, 14, 17, 24, 30-0=30일거다 +인곳에서는 L에서 가야하는거리빼주고 -인애는 가야하는 거리 만큼 위치해있다

5만큼 행진했을때

id[i]                    4   5   -1   -3   -2  6

P[i]또는 30-P[i]  +20 +17 -14 -17 -24  0 

P[i]                   10   13  14  17   24 30

id=6인 아이가 제일 첫번째로 떨어진다

이후에 행진의 주가 될 아이는 P[i]또는 30-P[i]에서 가장 작은 값인 14이다

근데 만약에 14만큼 행진을 바로 시키면 그 과정에 id=5와 id=-3인애가 충돌한다

충돌하는 경우는 id[i], id[j]라 할때 두 id 부호가 반대고 p[i]-p[j]의 절댓값이 짝수여야한다

id=5, -3인 두아이는 17-13=4로 부호가 반대고 거리가 짝수임으로 충돌한다 충돌하게 될 경우엔 방향을 바꾸게 되므로

id의 부호를 바꿔주고 서로의 가야하는 거리가 바뀌게 된다(배열에 따로 숫자로 바꿔줄필요없음)

행진하는 주된 아이를 고른다음 개미 한마리당 자기의 양옆에 부호가 다른 개미와 p[i]-p[j]를 구하고 그것의 절반보다 행진하는 거리의 크기가 크다면 충돌한다는 것을 찾아낼 수 있다

* 바로 시간초과...이렇게 찾아내는건 너무 비효율적인거같다 질문검색에 보니까 계산식을 아예 세워서 바로 하는 방법이 있던데 

계산은 어려우니까.. 패스... 채점중 14퍼에서 시간초과 뜬다

코드

cnt=0;

while(cnt != k){

j = L; //최소 행진해야하는 거리

y = 1;

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

if(p[i] == DROP)

continue;

if(id[i] > 0) //오른쪽으로 가야하는 아이라면

{

if(j > L-p[i] || (j == L-p[i] && a[i] <= a[y]) ) //실제로 행진해야하는 거리

{

j = L - p[i];

y = i;

}

}

else //왼쯕으로 가야하는 아이라면

{

if(j > p[i] || (j == p[i] && a[i] <= a[y]) ) //실제로 행진해야하는 거리

{

j = p[i];

y = i;

}

}

}

p[y] = DROP;  

cnt++;

for(i=1; i<=N; i++) //충돌하는경우찾기

{

for(b=i+1; b<=N; b++)

{

if(id[i]*id[b] < 0) //부호가 다를때

{

if( abs(p[i]-p[b])%2==0 && abs(p[i]-p[b])/2 <= j) //충돌!

{

if(id[i] > 0){

id[i] = -id[i];

id[b] = id[b] - 2*id[b];

break;

}

else

{

id[b] = -id[b];

id[i] = id[i] - 2*id[i];

break;

}

}

}

}

if(p[i] != DROP){ 

if(id[i] > 0 )

p[i] += j;

else

p[i] -= j;

}

}

if(cnt == k){

results[x]=a[y];

break;

}

}