[BOJ] 10158 개미 - JAVA

1. 문제

10158번: 개미

처음에 (p,q)에서 출발한 개미는 1시간 후에는 (p+1,q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.

여러분은 크기 w×h인 격자 공간에서 처음에 (p,q)에서 출발하는 개미의 t시간 후의 위치 (x,y)를 계산하여 출력해야 한다. 개미는 절대 지치지 않고 같은 속력으로 이동한다고 가정한다.

문제에서 w와 h는 자연수이며 범위는 2 ≤ w,h ≤ 40,000이다. 그리고 개미의 초기 위치 p와 q도 자연수이며 범위는 각각 0 < p < w과 0 < q < h이다. 그리고 계산할 시간 t의 범위는 1 ≤ t ≤ 200,000,000이다. 

---

2. 풀이

• 여러 번 풀었고 여러 번 틀렸다. 순서대로 코드를 공유한다.

1번 방식 - 시간초과

• 1초가 지날 때마다 변화를 주는 방식이다. 당연하지만 시간초과가 났다.

int dp = 1;
int dq = 1;
while (--T >= 0) {
	P = P + dp;
	Q = Q + dq;
	if (P == 0 || P == W) dp *= -1;
	if (Q == 0 || Q == H) dq *= -1;
}

2번 방식 - 99퍼센트에서 시간초과

• 1번 방식에서 조금 더 머리를 쓴 방식이다. 변화값이 0보다 크다면 P,Q가 W,H로 이동하고 0보다 작다면 P,Q가 0으로 이동한다. 따라서 도달하는 데 더 작은 시간(t)을 찾아서 T에서 뺀다. 
• 그 다음 P,Q 값을 쓴 시간(t)에 맞춰서 다시 설정한다.
• 만약 두 시간(tp,tq) 중에 tq가 작다면 경계선에 Q가 먼저 도달한 것이므로 dq변화값에 -1을 곱한다.
• tp가 작다면 경계선에 P가 먼저 도달한 것이므로 dp변화값에 -1을 곱한다.
• 둘이 같다면 같은 시간에 경계선에 도달한 것이므로 둘 다 -1을 곱한다.

int dp = 1;
int dq = 1;

while (T > 0) {
	int tp = dp > 0 ? W - P : P;
	int tq = dq > 0 ? H - Q : Q;

	int t = Math.min(tq, tp);
	t = Math.min(T,t);
	T -= t;

	P += dp * t;
	Q += dq * t;

	if (tp > tq) dq *= -1;
	else if (tp < tq) dp *= -1;
	else {
		dp *= -1;
		dq *= -1;
	}
}

3번 방식 - 통과

• 점 P에서 W*2만큼의 시간동안 움직인 후 위치를 보면 그대로 P에 있다. 점 Q에서도 마찬가지다.(H*2시간 동안)
• 따라서 시간 T를 각각 (W*2),(H*2)로 나눠서 그 나머지를 P와 Q에 더한다.
• 만약 그 두 값이 W,H를 벗어난다면 W,H의 두배에서 자기자신을 뺀 값을 절대값으로 씌운다.

P+=T%(W*2);
Q+=T%(H*2);
if(P>W) P=Math.abs(W*2-P);
if(Q>H) Q=Math.abs(H*2-Q);

4번 방식(3번 방식과 유사) 

• 3번 방식을 좀 더 간단하게 한 방식이다. (시간+내 위치)를 (W*2),(H*2)로 나누고 그 나머지를 W,H에서 뺀다. 새로운 값이 범위에서 벗어났는지 체크하기 위함이다.  

P = W-Math.abs(W-(T+P)%(2*W));
Q = H-Math.abs(H-(T+Q)%(2*H));

---

3. 결과

ㅎㅎ.. 다른 의미로 너무 어려운 문제였다.