3163번 - 떨어지는 개미
개미문제는 어떤방식으로 접근해야하는지 짐작이 가질 않습니다..
실제 개미의 움직임을 시뮬레이션 해야하는건가요?
만약 시뮬레이션해야 한다고 하면, 개미가 서로 만날 때 좌표가 어떻게되나요?
예를들어 시간 0에서 1,3 좌표에서 서로 출발하면 시간 1에 좌표 2에서 부딪힐 탠데, 이 땐 겹쳐졌다가 시간 2에 반대로 흩어지는건지와
시간 0에서 1,2 좌표에서 마주보고 출발하면 충돌할 때 어떻게 처리되는지 궁금합니다..
제가 푼 개미문제는
https://www.acmicpc.net/problem/4307
로 최대 최소만 구하면 되는.. 이런 류의 문제만 나오는줄 알았는데 아닌거같더군요..
답변 부탁드립니다.
개미가 부딪히면, 서로 가던 방향을 바꾸는 게 아니라, 인덱스만 교환한다고 생각하시면 문제 풀기가 쉬워집니다.
아, 어떻게 충돌하던지 인덱스만 바꾸는 방식이면 알아서 처리 되겠네요. 감사합니다 ㅎㅎ
@hongjun7 님이 말한 인덱스 교환이란 말이 이해가 안되네요.
개미의 인덱스 순서는 절대 바뀌지 않습니다.
4307번 개미 문제에서 처럼 개미가 떨어지는 시간을 구할 수 있습니다. 그리고 그 떨어지는 개미가 왼쪽 끝에서 떨어지는지, 오른쪽 끝에서 떨어지는지 구할 수 있습니다. 이제 개미의 인덱스의 순서는 절대로 바뀌지 않는 것을 알았을 때, 떨어지는 개미의 인덱스 또한 알 수 있습니다.
전체적으로 시뮬레이트 하지않고 각 개미마다 떨어지는 시간을 계산하는건가요? 저도 그렇게 풀려고 하다가
머리가 복잡해져서 시뮬레이트가 필요한가 생각한거였는데 좀 더 머리를 굴려봐야겠네요
아 제가 알던 문제랑 그림만 유사한 문제였네요ㅠㅠ 죄송합니다.
아 아니네요. 제가 생각했던 걸 표현을 잘못했었군요. 인덱스만 교환한다고 생각하면 떨어지는 시간을 알 수 있다는 말이었고, 그 시간을 알면 @myungwoo 님께서 말씀하신대로 풀 수 있군요. 제가 멍청해서 죄송합니다ㅠㅠ
구체적인 솔루션을 제시하지는 않지만, 개미의 순서가 변하지 않는다라는 것만 알면 쉬운 문제입니다. ㅋㅋ
인덱스를 바꾼다고해서 뭔소린가 햇는데 이해하니까 맞네요
댓글을 작성하려면 로그인해야 합니다.
yukariko 9년 전
개미문제는 어떤방식으로 접근해야하는지 짐작이 가질 않습니다..
실제 개미의 움직임을 시뮬레이션 해야하는건가요?
만약 시뮬레이션해야 한다고 하면, 개미가 서로 만날 때 좌표가 어떻게되나요?
예를들어 시간 0에서 1,3 좌표에서 서로 출발하면 시간 1에 좌표 2에서 부딪힐 탠데, 이 땐 겹쳐졌다가 시간 2에 반대로 흩어지는건지와
시간 0에서 1,2 좌표에서 마주보고 출발하면 충돌할 때 어떻게 처리되는지 궁금합니다..
제가 푼 개미문제는
https://www.acmicpc.net/problem/4307
로 최대 최소만 구하면 되는.. 이런 류의 문제만 나오는줄 알았는데 아닌거같더군요..
답변 부탁드립니다.