[JAVA] 백준 10158 - 개미

문제

가로길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w, h)이다. 이 공간 안의 좌표 (p, q)에 개미 한 마리가 놓여있다. 개미는 오른쪽 위 45도 방향으로 일정한 속력으로 움직이기 시작한다. 처음에 (p, q)에서 출발한 개미는 1시간 후에는 (p+1, q+1)로 옮겨간다. 단, 이 속력으로 움직이다가 경계면에 부딪치면 같은 속력으로 반사되어 움직인다.

위 그림은 6×4 격자에서 처음에 (4,1)에서 출발한 개미가 움직인 길을 보여주고 있다. 처음메 (4,1)에 있는 개미는 2시간 후에 (6,3)에 있으며 8시간 후에 (0,1)에 있다. 만일 그 개미가 처음에 (5,3)에 있었다면 매시간마다 (6,4), (5,3), (4,2), (3,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이다.

 

입력

첫줄에는 w와 h가 공백을 사이에 두고 주어진다. 그다음 줄에는 초기 위치의 좌표값 p와 q가 공백을 사이에 두고 주어진다. 3번째 줄에는 개미가 움직일 시간 t가 주어진다.

 

출력

출력은 t 시간 후에 개미의 위치 좌표 (x,y)의 값 x와 y를 공백을 사이에 두고 출력한다.

 

입출력 예제

 

알고리즘❓ 풀어내기❗️

1. 1 ≤ t ≤  200,000,000, 시간제한 0.15 등 입력 조건을 보면 O(1)로 풀어야 한다.
2. O(1)로 해결하려면 산술적, 정수적 규칙을 찾아내야 한다.
3. 가로 방향만 고려했을 때 p의 x좌표는 t시간 동안 항상 1이 증가 또는 감소한다.
4. 방향을 고려하지 않기 위한 왕복주기(제자리에 돌아옴)는 항상 2 * w이다.
5. 처음 시작 x와 t를 더한 왕복주기(2 * w)로 나눈 나머지가 현재 x의 위치다.
6. 여기에 x의 값이 w보다 크다면 이는 반주기(w)를 넘겼고, 방향은 현재와 반대이고, 값은 2w의 좌표를 기준으로 역 w - (x-w) = 2w-x이다.
7. 세로 방향도 가로와 같다.

 

🧑🏻‍💻코드 리뷰

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt();
        int H = sc.nextInt();
        int P = sc.nextInt();
        int Q = sc.nextInt();
        int T = sc.nextInt();

        int currentX = (T + P) % (2 * W);
        int currentY = (T + Q) % (2 * H);
        if (currentX > W) currentX = 2 * W - currentX;
        if (currentY > H) currentY = 2 * H - currentY;

        System.out.println(currentX + " " + currentY);
    }
}