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. 내 풀이(시간초과)

import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String input1 = sc.nextLine();
		String input2 = sc.nextLine();
		int inputT = sc.nextInt();
		int inputW = Integer.parseInt(input1.substring(0,1));
		int inputH = Integer.parseInt(input1.substring(2,3));
		int inputX = Integer.parseInt(input2.substring(0,1));
		int inputY = Integer.parseInt(input2.substring(2,3));
		
//		System.out.printf("input w: %d, input h: %d, input x: %d, input y: %d, input t: %d\n",inputW,inputH,inputX,inputY,inputT);
//		
		// 인풋받은 대로 좌표를 생성
		int t = 0;
		int w = inputW;
		int h = inputH;
		int x = inputX;
		int y = inputY;
		// 첫 좌표를 기억
		int startX = inputX;
		int startY = inputY;
		// 전 좌표를 기억
		int tempX=0;
		int tempY=0;
		
//		System.out.printf("초기위치: x:%d, y:%d, 현재시간: %d\n", startX, startY, t);
		while(t<inputT) {
			// 첫 번째 경우: x 오른쪽, y 위쪽 가야할 경우 (x++, y++)
			if((0<=startX && startX<w && 0<=startY && startY<h)||
					(x<tempX&&y>tempY&&x==0&&0<y&&y<h)||
					(x<tempX&&y<tempY&&x==0&&y==0)||
					(x>tempX&&y<tempY&&0<x&&x<w&&y==0)) {
				startX = -1;
				startY = -1;
				while(x<w && y<h && t<inputT) {
					tempX = x;
					tempY = y;
					x++;
					y++;
					t++;
//					System.out.printf("현재위치: x:%d, y:%d, 현재시간: %d, 이전좌표: (%d, %d)\n", x, y, t, tempX, tempY);
				}
			}
			// 두 번째 경우: x 오른쪽, y 아래쪽 가야 할 경우 (x++, y--)
			if((startX==0 && startY<=h&&0<startY)||
					(x>tempX&&y>tempY&&y==h&&0<x&&x<w)||
					(x<tempX&&y<tempY&&x==0&&0<y&&y<h)||
					(x<tempX&&y>tempY&&x==0&&y==h)) {
				startX = -1;
				startY = -1;
				while(x<w && 0<y && t<inputT) {
					tempX = x;
					tempY = y;
					x++;
					y--;
					t++;
//					System.out.printf("현재위치: x:%d, y:%d, 현재시간: %d, 이전좌표: (%d, %d)\n", x, y, t, tempX, tempY);
				}
			}
			// 세 번째 경우: x 왼쪽, y 위쪽 가야 할 경우 (x--, y++)
			if((startX==w&&0<=startY&&startY<h)||
					(tempX>x&&tempY>y&&y==0&&0<x&&x<w)||
					(tempX<x&&tempY>y&&x==w&&y==0)||
					(tempX<x&&tempY<y&&x==w&&0<y&&y<h)){
				startX = -1;
				startY = -1;
				while(0<x && y<h && t<inputT) {
					tempX = x;
					tempY = y;
					x--;
					y++;
					t++;
//					System.out.printf("현재위치: x:%d, y:%d, 현재시간: %d, 이전좌표: (%d, %d)\n", x, y, t, tempX, tempY);
				}
			}
			// 네 번째 경우: x 왼쪽, y 아래쪽 가야 할 경우 (x--, y--)
			if((0<startX&&startX<=w&&startY==h)||
					(tempX>x&&tempY<y&&y==h&&0<x&&x<w)||
					(tempX<x&&tempY<y&&x==w&&y==h)||
					(tempX<x&&tempY>y&&x==w&&0<y&&y<h)) {
				startX = -1;
				startY = -1;
				while(0<x && 0<y && t<inputT) {
					tempX = x;
					tempY = y;
					x--;
					y--;
					t++;
//					System.out.printf("현재위치: x:%d, y:%d, 현재시간: %d, 이전좌표: (%d, %d)\n", x, y, t, tempX, tempY);
				}
			}
		}
//		System.out.printf("완료 후 좌표: x: %d, y: %d, 소요시간: %d\n", x, y, t);
		System.out.printf("%d %d", x, y);
		
	}

}

 

 

2. 시간초과 문제를 해결하기 위해 수학적으로 문제를 풀고 input 방식을 bufferedreader 사용하여 새로 풀이한 정답:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class test6_1 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input1 = br.readLine().split(" ");
		String[] input2 = br.readLine().split(" ");
		String[] input3 = br.readLine().split(" ");
		int w = Integer.parseInt(input1[0]);
		int h = Integer.parseInt(input1[1]);
		int x = Integer.parseInt(input2[0]);
		int y = Integer.parseInt(input2[1]);
		int t = Integer.parseInt(input3[0]);
		
		int i = (x + t) % (2*w);
		int j = (y + t) % (2*h);
		
		if(i>w) {
			i = (2*w) - i;
		}
		if(j>h) {
			j = (2*h) - j;
		}
		
		System.out.printf("%d %d", i, j);
	}

}