백준 10158번: 개미 (JAVA)

문제

가로 길이가 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를 공백을 사이에 두고 출력한다. 

 

---

 

왜 틀렸는가?

이동 거리가 최대 2억번이기에 시뮬레이션을 돌리는 문제는 아닐 거라 짐작은 했다. 살짝 최적화하여, 한 칸씩 움직이지 않고 벽까지 한번에 움직이도록 구현하였다. 이후 'w, h의 범위가 40000이니까 2억/4만 == 5천번정도 연산하겠구나(???)'라는 이상한 사고회로에 따라 이 알고리즘은 시간 초과가 안 날거라고 생각했고, 당연히 시간 초과가 났다.

 

풀이

개미의 움직임은 LCM(2*w, 2*h)의 주기를 갖는다. 다만 w, h가 최대 4만이므로 최소공배수 값도 10억(w, h가 4만에 가까운 서로소일때)이 넘을 수 있다는 점이 문제이다.

그러므로 x의 움직임과 y의 움직임을 따로보는 게 필요하다. x좌표가 벽에 닿아서 팅겨지면 x방향 움직임은 바뀌지만, y방향 움직임은 바뀌지 않는다. 그리고 그 반대도 마찬가지.

따라서 x좌표는 2*w를 주기로 가지며, y좌표는 2*h를 주기로 갖는다. 그러므로, t%(2*w), t%(2*h)번만 움직여보면 된다. 위 알고리즘은, 한칸한칸 움직임을 구현한다고 해도 O(max(w, h))이므로 충분히 시간 여유가 있는 알고리즘이다.

 

 

코드

풀이 1 (움직임 시뮬레이션)

import java.util.Scanner;

public class Main {	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt();
		int H = sc.nextInt();
		int x =  sc.nextInt();
		int y = sc.nextInt();
		int t = sc.nextInt();
		x = move(x, t % (2*W), '+', W);
		y = move(y, t % (2*H), '+', H);
		System.out.println(x + " " + y);
	}

	
	public static int move(int x, int t, char direction, int size) {
		if (direction == '+') {
			if (t <= size-x) return x + t;
			return move(size, t-size+x, '-', size);
		}
		else {
			if (t <= x) return x - t;
			return move(0, t-x, '+', size);
		}
	}
}

 

풀이 2 (식으로 한 번에)

import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt();
		int H = sc.nextInt();
		int x =  sc.nextInt();
		int y = sc.nextInt();
		int t = sc.nextInt();
		System.out.println(Math.abs(W - Math.abs(W - x - t%(2*W))) + " " + Math.abs(H - Math.abs(H - y - t%(2*H))));
	}
}