[백준/수학] 10158 개미(Java, 자바)

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

10158번: 개미

 

 

 

이 문제는 시간복잡도가 아주 중요한 문제이다. 단순하게 생각하면 금방 풀 수 있지만, 그러면 대다수는 시간복잡도에 걸린다.

 

내가 처음으로 제출한 코드는 다음과 같다.

static void pro() {
    int deltaX = 1;
    int deltaY = 1;

    while (t-- > 0) {
        if (p == w) deltaX = -1;
        if (p == 0) deltaX = 1;
        if (q == h) deltaY = -1;
        if (q == 0) deltaY = 1;

        p += deltaX;
        q += deltaY;
    }
    sb.append(p).append(" ").append(q);
    System.out.println(sb);
}

 

단순하게 시간이 진행하는 동안 x, y의 좌표를 옮겨주고 경계선을 만나면 경로가 반전하는 식이다.

이렇게 제출하면 시간 복잡도를 만나게 된다.

 

여기서 어떻게 시간을 줄일지에 대해 생각해보자.

 

개미의 움직임을 관찰해보면 특정한 "주기"가 있음을 알게 된다. 다음 그림과 같이 개미의 주기는 24이다. (진행방향까지 고려한 주기를 생각해야한다.)

 

 

조금 더 관찰해보면 x의 주기와 y의 주기가 각각 있음을 알 수 있다. 

x의 주기는 높이*2이고, y주기는 너비*2이다. (방향까지 고려했을 때)

 

이제 주기를 구했으니 코드를 짤 수 있다. 그런데, 개미의 시작 위치가 0이 아니다보니 부가적인 계산이 들어간다.

이를 간단히 해결할 수 있는 방법이 있다.

 

바로 개미의 위치 만큼 시간을 더하는 것이다.

그렇다면 개미의 현재 위치는 다음과 같이 구할 수 있다.

현재 X 위치 = (처음 X 위치 + 이동시간) % (2 * 너비)
현재 Y 위치Y = (처음 Y 위치 + 이동시간) % (2 * 높이)

 

이를 모두 적용한 전체 코드는 다음과 같다.

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

public class boj_10158 {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int w, h, p, q, t;

	// 입력
    static void input() {
        w = scan.nextInt();
        h = scan.nextInt();
        p = scan.nextInt();
        q = scan.nextInt();
        t = scan.nextInt();
    }

	// 현재 위치를 구하기
    static void pro() {
        int currentX = (p + t) % (2 * w);
        int currentY = (q + t) % (2 * h);

        if (currentX > w) currentX = 2 * w - currentX;
        if (currentY > h) currentY = 2 * h - currentY;

        sb.append(currentX).append(" ").append(currentY);
        System.out.println(sb);
    }


    public static void main(String[] args) {
        input();
        pro();
    }

	// 입력을 받기 위한 클래스
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}