JAVA 백준 10158 개미 (수학)

 

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

---

문제

1. 첫째 줄에 좌표 ( w, h ) ( 2 <= w, h <= 40000 ) 이 공백으로 구분되어 입력된다.
2. 둘째 줄에 좌표 ( p, q ) ( 0 < p < w , 0 < q < w ) 이 공백으로 구분되어 입력된다.
3. 셋째 줄에 시간 t ( 1 <= t <= 200000000 ) 이 입력된다.
4. 개미는 ( p, q ) 에서 시작하여 t시간동안 움직여 끝에 닿으면 반사되어 움직이며, t시간이 지난 후 마지막에 도착한 위치를 출력하게 된다.

---

 

 

초기 코드

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

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());

        boolean xFlag = false;
        boolean yFlag = false;

        for (int i = 0; i < t; i++) {
            if (p == w) {
                xFlag = true;
            } else if (p == 0) {
                xFlag = false;
            }

            if (q == h) {
                yFlag = true;
            } else if (q == 0) {
                yFlag = false;
            }

            if (xFlag) {
                p--;
            } else {
                p++;
            }

            if (yFlag) {
                q--;
            } else {
                q++;
            }
        }

        System.out.println(p + " " + q);
    }
}

 

반복문으로 계산해서 그런지 시간 초과가 났다.

반복문에서 개미의 현 좌표가 격자의 끝에 닿을 때 방향을 꺾어 진행할 수 있도록 한다.

 

시간 복잡도가 t인데 t가 최대 2억이라 시간 초과가 난다.

 

이 때 개미의 대각선 이동은 X축 이동과 Y축 이동을 합친 것으로 따로 계산하여 합칠 수 있다.

 

 

정답 코드

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

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 xTime = t % (2 * w);
        int yTime = t % (2 * h);

        boolean xFlag = false;
        boolean yFlag = false;

        for (int i = 0; i < xTime; i++) {
            if (p == w) {
                xFlag = true;
            } else if (p == 0) {
                xFlag = false;
            }

            if (xFlag) {
                p--;
            } else {
                p++;
            }
        }

        for (int i = 0; i < yTime; i++) {
            if (q == h) {
                yFlag = true;
            } else if (q == 0) {
                yFlag = false;
            }

            if (yFlag) {
                q--;
            } else {
                q++;
            }
        }

        System.out.println(p + " " + q);
    }
}

 

 

대각선으로 가는 것이 아닌 가로와 세로 방향으로 나누어 각각의 x좌표와 y좌표를 구해 출력하는 방법이다.

 

개미가 똑같은 패턴을 반복하므로 여러 번 겹치는 패턴을 모두 생략하고 마지막에 도착점까지 가는 부분만 구하여 출력하니 시간 초과가 나지 않았다.