yukariko   9년 전

개미문제는 어떤방식으로 접근해야하는지 짐작이 가질 않습니다..

실제 개미의 움직임을 시뮬레이션 해야하는건가요?

만약 시뮬레이션해야 한다고 하면, 개미가 서로 만날 때 좌표가 어떻게되나요?

예를들어 시간 0에서 1,3 좌표에서 서로 출발하면 시간 1에  좌표 2에서 부딪힐 탠데,  이 땐 겹쳐졌다가 시간 2에 반대로 흩어지는건지와

시간 0에서 1,2 좌표에서 마주보고 출발하면 충돌할 때 어떻게 처리되는지 궁금합니다..

제가 푼 개미문제는 

https://www.acmicpc.net/problem/4307

로 최대 최소만 구하면 되는.. 이런 류의 문제만 나오는줄 알았는데 아닌거같더군요..

답변 부탁드립니다.

h0ngjun7   9년 전

개미가 부딪히면, 서로 가던 방향을 바꾸는 게 아니라, 인덱스만 교환한다고 생각하시면 문제 풀기가 쉬워집니다.

yukariko   9년 전

아, 어떻게 충돌하던지 인덱스만 바꾸는 방식이면 알아서 처리 되겠네요. 감사합니다 ㅎㅎ

myungwoo   9년 전

@hongjun7 님이 말한 인덱스 교환이란 말이 이해가 안되네요.

개미의 인덱스 순서는 절대 바뀌지 않습니다.

4307번 개미 문제에서 처럼 개미가 떨어지는 시간을 구할 수 있습니다. 그리고 그 떨어지는 개미가 왼쪽 끝에서 떨어지는지, 오른쪽 끝에서 떨어지는지 구할 수 있습니다. 이제 개미의 인덱스의 순서는 절대로 바뀌지 않는 것을 알았을 때, 떨어지는 개미의 인덱스 또한 알 수 있습니다.

yukariko   9년 전

전체적으로 시뮬레이트 하지않고 각 개미마다 떨어지는 시간을 계산하는건가요? 저도 그렇게 풀려고 하다가

머리가 복잡해져서 시뮬레이트가 필요한가 생각한거였는데 좀 더 머리를 굴려봐야겠네요

h0ngjun7   9년 전

아 제가 알던 문제랑 그림만 유사한 문제였네요ㅠㅠ 죄송합니다.

h0ngjun7   9년 전

아 아니네요. 제가 생각했던 걸 표현을 잘못했었군요. 인덱스만 교환한다고 생각하면 떨어지는 시간을 알 수 있다는 말이었고, 그 시간을 알면 @myungwoo 님께서 말씀하신대로 풀 수 있군요. 제가 멍청해서 죄송합니다ㅠㅠ

pl0892029   9년 전

구체적인 솔루션을 제시하지는 않지만, 개미의 순서가 변하지 않는다라는 것만 알면 쉬운 문제입니다. ㅋㅋ

blutics   6년 전

인덱스를 바꾼다고해서 뭔소린가 햇는데 이해하니까 맞네요

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