[백준] 10158 개미

1. 문제

www.acmicpc.net/problem/10158

10158번: 개미

2. 접근방법

삽질 1

처음 접근은 시뮬을 돌리다 순환되는 위치를 찾으면

그 순환으로 시간의 mod를 구한 후 나머지 만큼만 가는 방법으로 풀었는데

시간초과 떴다 ... 0.15초면 1500만번은 하지 않나 ..?  

 

삽질 2

그래서 공식이 있으려나 싶어서 찾아보니 순환이 생기게 되는 횟수가 맵의 크기에 비례하더라

맵의 W랑 H 값이 같으면 W+H 번째에 처음과 똑같은 위치로 오고

W와 H 값이 다를 땐 H*W*2 번째에 똑같은 위치로 돌아오는 것을 발견했다.

그래서 순환값을 바로 구해서 t의 mod를 바로 구해서 나머지만큼만 시뮬을 돌렸는데 

이것도 시간초과 돼서 계산을 다시 해보니 최악 16억 - 1 만큼 연산 해야 하더라 ;;

 

해법

순환을 생각하다보니 어차피 

1초에 가는 건 어디로든 가로 1칸 세로 1칸씩 이동하네?

 

가로랑 세로 따로 따로 보니 훨씬 쉽게 접근이 가능했다.

 

우선 가로로만 봐보면

p위치에서 T만큼 오른쪽으로 가다가 벽만나면 반대로 가다가 벽만나면 계속 왔다갔다 하는데

2W만큼 움직일 때마다 다시 0으로 돌아오는 걸 알 수 있다.

즉 그냥 P+T만큼을 0에서 부터 출발한다고 생각하고

(P+T) % 2W 만큼 가는 위치랑 같다.

 

 

 

그리고 최종 x좌표를 구할때는  나머지의 값이

W보다 작을 때는 그냥 나머지이고 W보다 크다면 2W - 나머지를 해줘야 한다.

 

이거를 식으로 간단히 하면 W - abs( W - mod( P+T , 2W) ) 이렇게 된다.

 

H 값도 똑같은 방식으로 H - abs( H - mod( q+T , 2H) ) 하면 된다.

3. 풀이

q값 p값에 대해 위 공식만 적용하면 되므로 패쓰

4. 자바 코드

package Silver;

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

public class P10158개미 {
	
	static int dr[] = {1,1,-1,-1};
	static int dc[] = {1,-1,-1,1};
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int W = Integer.parseInt(st.nextToken());
		int H = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		int q = Integer.parseInt(st.nextToken()); //q가 컬럼
		int p = Integer.parseInt(st.nextToken()); //p가 로우
		int t = Integer.parseInt(br.readLine());
		int x = (q+t)%(2*W);
		int y = (p+t)%(2*H);
		
		x = W - Math.abs(W-x);
		y = H - Math.abs(H-y);
		
		System.out.println(x+" "+y);
	}

}

5. 마치며

삽질을 진짜 오래한 문제

복잡한 구현 문제를 푸는 것보다 이런 수학개념으로 식을 도출해내는 문제가 훨씬 어려운 것 같다..