BOJ 10158 - 개미

문제

W x H 격자 위에서 개미가 대각선(45도)으로 이동하며 벽에 부딪히면 반사된다. 초기 위치 (P, Q)에서 T초 후 개미의 위치를 구하라.

입력

첫째 줄에 W, H, 둘째 줄에 P, Q, 셋째 줄에 T가 주어진다.

출력

T초 후 개미의 x, y 좌표를 출력한다.

예제

입력	출력
`6 4` `4 1` `8`	`0 1`

풀이

x축과 y축을 독립적으로 처리하여 반사 이동 후 위치를 수학적으로 계산한다.

x좌표와 y좌표를 독립적으로 계산한다 (대각선 이동은 x, y 각각 ±1)
(P+T)/W의 몫이 짝수이면 (P+T)%W, 홀수이면 W-(P+T)%W가 x좌표이다
y좌표도 동일한 방식으로 H를 기준으로 계산한다

핵심 아이디어: 벽 반사는 주기적 패턴이므로, 주기(2W, 2H) 내에서 현재 방향(짝수/홀수 구간)에 따라 좌표를 결정한다.

코드

package day499;
 
import java.io.*;
import java.util.*;
 
public class Day476BOJ10158개미 {
  static int W, H, P, Q, T;
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    W = Integer.parseInt(st.nextToken());
    H = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());
    P = Integer.parseInt(st.nextToken());
    Q = Integer.parseInt(st.nextToken());
    T = Integer.parseInt(br.readLine());
    int x = (int) (P + T) / W % 2 == 0 ? (P + T) % W : W - (P + T) % W;
    int y = (int) (Q + T) / H % 2 == 0 ? (Q + T) % H : H - (Q + T) % H;
 
    System.out.println(x + " " + y);
  }
}

복잡도

시간: O(1)
공간: O(1)

문제