[BJ] 백준 10158 개미(JAVA)

문제

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

 

풀이 방법

문제를 간단하게 이해하면 t초후 개미의 위치를 구하면 되는 문제다. 이동은 45도로 이동을 하기 때문에 물론 이동 방향을 사용해서 하면 어려운 문제는 아니다.
하지만 이 문제에서 그런식으로 문제를 푼다면 시간초과가 난다. 시간을 단축시킬 수 있는 다른 방법을 찾아야한다. 나도 처음엔 위와 같은 방식으로 문제를 풀었는데 시간초과가 났고, 어떤 식으로 풀어야할 지 계속해서 고민을 한 것 같다. 
몇시간을 고민하면서 시도를 했었는데 도저히 풀리지가 않아서 힌트를 조금 얻어서 풀었다.
내가 본 힌트는 x와 y좌표를 따로 구해보라 였다. 
그래서 어떻게 따로 구하지 생각을 하다가 x좌표만 가지고 보니 좌표가 열 길이의 2배만큼 이동을 하면 제자리도 돌아오는 걸 알 수 있었다. 그래서 생각한 방법이 x,y 좌표 모두 각각 행, 열 길이에 맞춰서 나눠주고 그 나머지를 이제 이동을 하면 계산을 줄일 수 있다는 생각이 들었다.

문제 풀이 순서
1. 시간을 행 길이의 2배만큼 나눠준다. 열도 마찬가지. 
2. 이제 각각 구해진 시간에 따라서 x와 y를 이동한다.
2. x좌표인 경우 점점 오른쪽으로 이동하고 오른쪽벽에 부딪치면 왼쪽으로 이동한다.  왼쪽 벽에 부딪치면 오른쪽으로 이동한다.
3. y도 동일하게 실행

 

제출 코드

import java.io.*;
import java.util.StringTokenizer;

public class BJ_10158_개미 {
	public static int w, h, t;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		w = Integer.parseInt(st.nextToken()); // 열
		h = Integer.parseInt(st.nextToken()); // 행

		st = new StringTokenizer(br.readLine());
		int p = Integer.parseInt(st.nextToken()); // 열 좌표
		int q = Integer.parseInt(st.nextToken()); // 행 좌표

		st = new StringTokenizer(br.readLine());
		t = Integer.parseInt(st.nextToken()); // 시간
		
		int xt = t % (2*w); //열
		boolean flag = false;
		for (int i = 0; i < xt; i++) {
			//flag가 true인 경우에는 1씩 감소 , false인 경우에는 1씩 증가 벽에 부딪치는 경우를 구현
			if(!flag) p++;
			else p--; 
			if(p==w) flag=true;
			else if(p == 0 ) flag = false; 
		}
		int yt = t % (2*h); //행
		flag = false;
		for (int i = 0; i < yt; i++) {
			if(!flag) q++;
			else q--; 
			if(q==h) flag=true;
			else if(q == 0 ) flag = false; 
		}
		System.out.println(p+" "+q);
	}
}