[BOJ][JAVA] 10158: 개미

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

10158번: 개미

import java.io.*;

class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] map = br.readLine().split(" ");
        int w = Integer.parseInt(map[0]);
        int h = Integer.parseInt(map[1]);
        String[] start = br.readLine().split(" ");
        int p = Integer.parseInt(start[0]);
        int q = Integer.parseInt(start[1]);
        int t = Integer.parseInt(br.readLine());
        // p가 0, w에 닿으면 다음 이동은 (반전, 그대로) q가 0,h에 닿으면 (그대로, 반전)
        int dir = 0; // 0, 1, 2, 3 시계방향 순서대로

        for(int i=0; i<t; i++){
            if(i!=0 && p == Integer.parseInt(start[0]) && q == Integer.parseInt(start[1])){
                if (t%i == 0) break;
                else{
                    t = t%i;
                }
            }
            switch (dir){
                case 0: {
                    // + +
                    p++;
                    q++;
                    if (p == w) dir = bounceX(0);
                    if (q == h) dir = bounceY(0);
                    if(p==w && q==h) dir = 2;
                }
                break;
                case 1: {
                    // + -
                    p++;
                    q--;
                    if (p == w) dir = bounceX(1);
                    if (q == 0) dir = bounceY(1);
                    if(p==w && q==0) dir = 3;
                }
                break;
                case 2: {
                    // - -
                    p--;
                    q--;
                    if (p == 0) dir = bounceX(2);
                    if (q == 0) dir = bounceY(2);
                    if(p==0 && q==0) dir = 0;
                }
                break;
                case 3: {
                    // - +
                    p--;
                    q++;
                    if (p == 0) dir = bounceX(3);
                    if (q == h) dir = bounceY(3);
                    if(p==0 && q==h) dir = 1;
                }
                break;
            }
        }

        System.out.printf("%d %d",p,q);
    }

    static int bounceX(int dir){
        int next = 0;
        switch (dir){
            case 0: {
                // + + 이게 이전 상태, 다음 상태로 가려면?
                next=3;
                break;
            }
            case 1: {
                // + -
                next=2;
                break;
            }
            case 2: {
                // - -
                next=1;
                break;
            }
            case 3: {
                // - +
                next=0;
                break;
            }
        }
        return next;
    }

    static int bounceY(int dir){
        int next = 0;
        switch (dir){
            case 0: {
                // + + 이게 이전 상태, 다음 상태로 가려면?
                next=1;
                break;
            }
            case 1: {
                // + -
                next=0;
                break;
            }
            case 2: {
                // - -
                next=3;
                break;
            }
            case 3: {
                // - +
                next=2;
                break;
            }
        }
        return next;
    }
}

---

오답노트(푸는 동안 사고과정 및 개선점)

경우의 수를 촘촘히 짜서 진행 방향을 바꿔주는 방식으로 설계했다... 예시는 다 맞았고 시간초과가 나버렸다.

다시 출발지점에 도착하는 경우로 설계해서 제출해봤지만 여전히 시초가 났다.

---

정답코드

import java.io.*;

class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] map = br.readLine().split(" ");
        String[] start = br.readLine().split(" ");
        int W = Integer.parseInt(map[0]);
        int H = Integer.parseInt(map[1]);
        int P = Integer.parseInt(start[0]);
        int Q = Integer.parseInt(start[1]);
        int T = Integer.parseInt(br.readLine());

        int p = (P + T) % (2 * W);
        int q = (Q + T) % (2 * H);
        if (p > W) p = 2 * W - p;
        if (q > H) q = 2 * H - q;
        System.out.println(p + " " + q);
    }
}

 

도착하는 게 능사가 아니라 출발지점에서 출발 방향도 같을 때를 고려했어야됐다. 그리고 주기를 구하는 게 중요한데, 그냥 대각선(이동)을 기준으로 주기를 잡으려면 무조건 시간초과가 난다.

X, Y좌표의 주기를 각각 관찰하면,

X가 방향이 같은 좌표에 도착하는 주기가 p = (T%2W)*N 이고 Y좌표는 q = (T%2H)*N 이 된다. 그리고 주기를 구할 때 X좌표 Y좌표를 분리시키면 시간 복잡도가 X, Y 둘중 큰 값으로 귀속되니까 이 방법으로 작성하면 시간초과가 나지않는다..!

 

출발지점이 지금은 (0,0)이 아닌데 출발지점을 원점으로 땡겨서 보면 주기를 아주 빨리 구할 수 있게된다. 이때 땡기는 정도가 초기 좌표만큼이기때문에 시간 조절을 잘 해야한다. p, q 가 W, H 보다 클 때 2*W-p 작업을 해주는 이유가 그 때문이다.

 

위 정답코드는 놀랍게도 시간초과가 난다..!

그 이유는 java 버전에 따른 오차로, 11로 했을때는 시간초과, 8로 했을때는 무사히 채점완료가 된다.

 

 

"댓글, 공감 버튼 한 번씩 누르고 가주시면 큰 힘이 됩니다"