문제 쪼개기 : 대각선 x,y 분해 - 벡터 (BOJ 10158 개미)

처음 생각한 방법 : 시뮬레이션

Direction 정하고 벽에 부딪힐때 방향이 어떻게 바뀌는지 함수 짜고 한 다음 T초 시뮬레이션 돌렸는데 당연히 TLE.

T max = 2억이므로, 1초 안에 모든 시뮬레이션 돌리기 힘듬.

 

근데, 벽에 부딪히지 않을때는 굳이 한틱씩 시뮬레이션 돌릴 필요 없으므로, 벽에 부딪혀서 방향 바뀌는 경우만 계산해줬더니 통과함.

 

하지만, 문제를 다른 관점에서 보면 굉장히 쉬워진다.

개미의 움직임을 벡터로 생각해보자.

$ \vec{v} = (x,y) $

출저 : https://hanstemcell.tistory.com/entry/%EB%B0%B1%EC%A4%80-%EA%B0%9C%EB%AF%B8

일단 x축만 생각해보면, 시작 지점에서 2*w 만큼 움직이면 다시 제자리로 돌아온다.

매 초마다 1만큼 움직이므로, 총 이동 거리는 T, 그러나 실제로 의미있는 이동거리는 T%(2*w). 

 

개미 초기 위치 x에서 이동 거리 T%(2*w)를 더해주면, x=w에 있는 벽을 넘어서는 경우가 생긴다.

우리가 필요한건 벽에 부딪쳐서 되돌아갈때 개미의 x좌표 위치라서, 보정을 좀 해줘야 한다.

 

여기서 3가지 Case를 생각해볼 수 있다.

 

Case 1. $x+T \% (2*w) \leq w$

)

보다시피, x+T%(2*w) 자체가 답이 된다.

 

Case 2. $w \lt x+T \leq 2*w $

x+T%(2*w)가 w를 넘어선걸로 표시가 되는데, 사실 벽에 부딪쳐서 돌아가야 한다.

저 답을 구하는 식을 짜보면,

Case 3. $ x+T \geq 2*w $

T가 w보다는 크고 2w보다는 작은 상황이다. 실제로는 x=0에 튕겨서 돌아오는 상황이다.

 

저 좌표를 구하는건 간단하다.

절댓값을 붙인다면 Case 2와 답을 같게 만들 수 있다.

 

그럼 Case 1과 2 & 3, 이렇게 두 경우로 나눠야 하나?

아니다. 절댓값을 활용하면 모든 Case의 답을 하나로 합칠 수 있다.

 

사실 위 원리를 이해했다면, x+T 자체의 주기를 생각해볼 수 있다.

어떻게? 

개미가 x=0에서 출발한다고 바꿔 생각하면, 문제에서 주어지는 p 라는 초기 위치 또한 개미가 x=0 으로부터 이동한 거리 p라고 생각할 수 있기 때문이다. 이후 T초간 더 움직였다고 할때, x+T 라는 개미가 움직인 거리값 자체가 2*w의 주기를 띠게 된다. 

 

이 경우는 x+T가 w보다 작을 때랑 클 때, 두 가지 경우만 생각하면 되고, 답은 아래와 같다.

절댓값 기호가 하나 사라지니, 더 깔끔한 것 같기도 하다.

 

 

또, y좌표랑 x좌표를 엮어서 생각할 필요가 없다. x,y는 서로 독립적으로 움직인다고 볼 수 있다. ★★★

비슷한 원리로 y좌표 움직임, y+T 의 주기는 2*h 이고, 동일한 식을 도출해낼 수 있다.

이렇게, 굳이 시뮬레이션 안하고도 간단한 사칙연산으로 바로 풀 수 있다.

 

 

교훈) 다양한 경험을 해서 이런 걸 잘 캐치하자.

 

 

---

BOJ 20056 마법사 상어와 파이어볼

 

파이어볼이 대각선으로 날아가는데, 맵 바깥으로 나가도 반대편으로 다시 돌아오도록 구현해야 함.

대각선 움직임을 구현하려면 머리 빠개짐.

대각선으로 움직일때의 주기? 시작점에 따라 달라지고, 이거 다 고려해서 구하기 까다로움

=> 일단, x와 y좌표를 분리해서 생각.

 

x 좌표만 생각해보자. 움직인 거리를 더해줬을 때 맵 밖으로 나간다면, 반대쪽으로 나오는 좌표를 어떻게 구할까?

맨 처음 위치 (파란 공) (2,4) 이고, → 방향으로 3만큼 움직인다고 하자.

사실 맵 바깥으로 나가면, 돌아서 (1,2) (빨간공)에 와야 하지만, 단순히 좌표에 움직인 거리를 더해주면 (2, 4 + 3)가 된다.

 

이때, 4 + 3을 가로 방향 (← →) 움직임의 주기인 5로 나눠주면, 2가 나오는데, 이게 바로 빨간공의 위치.

 

왜?) 숫자 N을 주기로 나눈다 = N에서 주기만큼을 계속 빼준다; 주기보다 작은 값이 나올 때 까지

위 그림에서 주기만큼을 빼주면, 파란공이 맵을 돌아서 움직여야하는 거리가 정확히 구해짐.

그래서 주기로 나눈 나머지가 빨간공의 위치가 되는 것!

 

만약 움직임이 999 같이 엄청 큰 수여도, 주기로 나눈 나머지가 답이 된다

(엄청 큰 수여도, 주기 만큼 계속 빼주다보면 위 상황과 같게 됨)

 

* N을 K로 나눌때 나머지를 구한다 (N % K) == N에서 K를 계속 빼준다. 값이 K보다 작아질 때 까지