백준 - 10158번(개미)

문제 출처: https://www.acmicpc.net/problem/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이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        
        int W = Integer.parseInt(tokenizer.nextToken()); // 열
        int H = Integer.parseInt(tokenizer.nextToken()); // 행
        tokenizer = new StringTokenizer(reader.readLine());
        int X = Integer.parseInt(tokenizer.nextToken()); // x 좌표
        int Y = Integer.parseInt(tokenizer.nextToken()); // y 좌표
        tokenizer = new StringTokenizer(reader.readLine());
        int T = Integer.parseInt(tokenizer.nextToken()); // 시간

        int resultX = (X + T) % (W * 2);
        int resultY = (Y + T) % (H * 2);

        if (resultX > W) resultX = W * 2 - resultX;
        if (resultY > H) resultY = H * 2 - resultY;

        System.out.println(resultX + " " + resultY);
    }

}

• 처음에 간단히 생각하고 풀었으나 여러가지 경우를 고려하지 못해 실패했다.
• 도저히 방법이 생각나지 않아 구글링을 통해 알게 된 방법은, 이동하는 행과 열을 각각 2배하여 계산하는 것이다. 그러면 개미가 한쪽 끝에서 출발하여 다른 한쪽 끝을 찍고 다시 출발점으로 돌아오는 것(2 W 이동, 2 H 이동)을 나머지 연산을 통해 쉽게 구할 수 있다. 만약 나머지가 W 보다 크다면 개미는 반대로 진행하는 것이므로 적절하게 처리한다.