[10158] 개미 - 구현, 수학 (백준, 자바, java)

아 정말 어렵게 풀었다. 주기성이 이해가 안 돼서 다음날까지 끌고옴. 해결컨셉은 반복 주기성을 파악하는 것.

 

▶️처음 든 생각

개미의 이동을 분석해서 bfs나 dfs를 적용해서 푸는 건 줄 알았는데 그렇게 하면 무조건 시간 초과가 나고 t시간 후의 이동을 직접 하나하나 시뮬레이션 하는 것이 아니고 규칙을 찾아서 계산하는 문제였다.

 

 

▶️Concept

X와 Y좌표를 독립적으로 생각하는 것이 첫 단추이다.

길이가 5인 수직선이 있다고 했을 때 X좌표만 가정해서 생각해보면

0에서 출발하면 t = 5 일때 5의 위치에, t = 10이면 다시 제자리인 0으로 돌아오게된다.

 

결국 그럼 개미의 움직임은 2w, 2h 주기로 반복됨을 알 수 있다.

 

(뭔가 이걸 보면서 요세푸스 문젠가 ? 원형으로 사람 5명이 둘러 앉았을때 나머지 연산을 통해 3번째와 8번째가 동일한 사람인 것을 도출해 내던 문제가 생각났다.)

따라서 1억 시간이든, 100억 시간이든 % 2w or 2h를 통해 제자리로 오는 시간을 다 쳐내고 실질적으로 초기 위치에서 몇 칸 이동했는 지만 구해주면 된다.

 

따라서 다음과 같은 코드를 도출할 수 있다.

remainX = (p + t) % (2 * w);
remainY = (q + t) % (2 * h);

 

이건 이제 초기 위치에서 몇 칸이나 떨어져있냐 ! 의 의미인데

중요한 건 2 * w 또는 2 * h로 나눈 나머지이기 때문에 다음과 같은 범위의 값이 나온다.

 

0 ≤ remainX < 2w, 0 ≤ remainY < 2h

0~w일 때는 양수 방향으로 가고 있다는 뜻이 되고

w ~ 2w일 때는 벽에 부딪혀서 음수방향으로 다시 돌아온다는 뜻이 된다.

 

따라서 조건을 설정해 최종 정답을 도출해야한다.

if (remainx >= 0 && remainX <= w) {
	finX = remaixX; 
	// 초기 + t시간 이동거리를 구했고 그게 정해진 격자 범위에 있으므로 그대로 정답값이된다.
	} else {
		finX = 2 * w - remainX;
	// w ~ 2w일 경우 이어 붙인 수직선에서 이동한 값을 빼주면
	// 다시 돌아온 좌표를 도출할 수 있다.
}

 

 

▶️Solution Code

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

public class Main {
    public static void main(String[] args) throws IOException{
        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 p = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        
        int t = Integer.parseInt(br.readLine());

        int remainX = (p + t) % (2 * w);
        int remainY = (q + t) % (2 * h);

        int curX = 0;
        int curY = 0;
        if (remainX >= 0 && remainX <= w) {
            curX = remainX;
        } else {
            curX = 2 * w - remainX;
        }
        
        if (remainY >= 0 && remainY <= h) {
            curY = remainY;
        } else {
            curY = 2 * h - remainY;
        }
        System.out.println(curX + " " + curY);
        br.close();
    }
}

이 간단한게 너무너무 이해가 안 됐다 ㅜㅜ!!!!!

다음 비슷한 문제가 나왔을 때 이해할 수 있길 바라며 .,,..,,