[백준] 10158번 : 개미 - 자바(JAVA)

https://www.acmicpc.net/problem/10158

10158번: 개미

 

문제 해석

개미가 2차원 공간에서 움직이는데 경계면에 부딪히면 반사되어 움직입니다. (초기 방향 = 오른쪽 위 45도)

개미는 1시간마다 이동합니다.

t시간 이후에 개미의 좌표를 출력하세요

 

문제 풀이 전 설계

 

 

개미는 오른쪽위/ 왼쪽 위/ 오른쪽 아래/ 왼쪽 아래로 움직입니다.

하지만 오른쪽위로 가다가 어느 벽에 부딪히느냐에 따라 방향이 달라지기 때문에 이점을 고려해야 합니다.

만약 오른쪽 위로 가다가 오른쪽벽에 부딪히면 왼쪽위로 이동합니다.

하지만 오른쪽위로 가다가 위에 벽에 부딪히면 왼쪽 아래로 이동합니다.

 

 

(왼쪽 벽, 오른쪽 벽, 아래 벽, 윗벽) * 2 = 8

 

시간제한이 0.15초이며 t의 범위가 1~2억이기 때문에 단순히 반복문을 통해서 해결할 순 없을 것 같다.

개미의 위치를 계속 기록하기보다는 방향에 따라 빼기 연산을 통해 시간을 줄여야 합니다.

 

위의 방식으로 개미를 한 칸씩 이동시킨다면 무조건 시간 초과가 나옵니다.

 

가로, 세로 움직임을 따로 생각해야 합니다.

가로로는 오른쪽, 왼쪽으로 움직이며 만약 0,0에서 시작했다고 가정했을 때 w*2만큼의 시간이 경과하면 다시 제자리로 돌아옵니다.

세로도 마찬가지로 h*2만큼의 시간이 경과하면 다시 제자리로 돌아옵니다.

따라서 가로/세로를 w*2 , h*2만큼 mod 연산을 해주고 나머지만큼만 더 움직여주게 된다면 값을 구할 수 있습니다.

 

 

코드

 

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

public class Main_10158_개미 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int width = Integer.parseInt(st.nextToken());
		int height = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine(), " ");
		int currentX = Integer.parseInt(st.nextToken());
		int currentY = Integer.parseInt(st.nextToken());

		int time = Integer.parseInt(br.readLine());

		int moveX = time % (width * 2);
		int moveY = time % (height * 2);

		int tempX = 1;
		int tempY = 1;
		// moveX > 0 || moveY > 0
		while (moveX > 0 || moveY > 0) {

			if (moveX > 0) {
				currentX += tempX;
			}
			if (moveY > 0) {
				currentY += tempY;
			}

			if (currentX == width)
				tempX = -1;
			if (currentX == 0)
				tempX = 1;
			if (currentY == height)
				tempY = -1;
			if (currentY == 0)
				tempY = 1;

			moveX--;
			moveY--;
		}

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

}

 

 

 

 

 

출처

https://lovelyunsh.tistory.com/25

[백준] 10158 개미