[JAVA]BOJ 10158

문제

이 문제는.. 엄청 어렵지는 않았는데 다른 의미로 까다로웠다..

1. 시간초과 나지 않는 알고리즘, 2. Scanner대신 BufferReader사용

import javax.swing.plaf.ColorUIResource;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ10158 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String size, current;
        String[] sizeStr, currentStr;
        int w, h, p, q, hour, resultP, resultQ;

        size = bf.readLine();
        current = bf.readLine();
        sizeStr = size.split(" ");
        currentStr = current.split(" ");

        w = Integer.parseInt(sizeStr[0]);
        h = Integer.parseInt(sizeStr[1]);
        p = Integer.parseInt(currentStr[0]);
        q = Integer.parseInt(currentStr[1]);
        hour = Integer.parseInt(bf.readLine());

        resultP = (p + hour) % (2 * w);
        resultQ = (q + hour) % (2 * h);

        if(resultP > w)
            resultP = w - (resultP - w);
        if(resultQ > h)
            resultQ = h - (resultQ - h);
            
        /* // 처음생각한 코드, 시간초과 발생
        resultP = p + hour;
        resultQ = q + hour;

        while((resultP<0||resultP>w)||(resultQ<0||resultQ>h)){
            if(resultP > w)
                resultP = w - (resultP - w);
            if(resultQ > h)
                resultQ = h - (resultQ - h);
            if(resultQ < 0)
                resultQ *= -1;
            if(resultP < 0)
                resultP *= -1;
        }
         */

        System.out.println(resultP + " " + resultQ);
    }
}

주석처리된 부분이 내가 처음에 짠 코드이다. 그냥 hour를 더하고 거울처럼 반사시켜서 정점에 다다르게 하려고 했다. 근데 시간초과도 발생했고 입력도 Scanner를 써서 느렸다. Scanner사용이 문제인가 싶어서 BufferedReader를 써봤는데.. 버퍼리더 코드도 잘못짰었고 수정해서 제출했더니 알고리즘 자체도 시간초과였다. 그래서 고민하다가.. 강의를 들었다.

 

개미가 지나가는 길은 동일하다. 즉 앞으로 계속 가다보면 모든 길을 다 돌아서 시작점으로 돌아온다는 것이다. 이것을 이용한다.

강의자료 첨부

우측에 있는 글처럼 27시간 뒤의 개미의 위치와 3시간 뒤의 개미의 위치는 같다. 이를 간단하게 식으로 표기하면 '도착점 = (시작점 + 시간) % x축(혹은 y축)*2' 가 된다. 그렇게 구한 값은 '도착 위치'가 아니라 '27시간 뒤 위치는 3시간 뒤 위치랑 같아!!' 이므로 3시간 뒤의 위치를 따로 구해주어야 한다. 방법은 여러가지가 있지만 내가 처음에 생각한 거울에 반사하는(?) 알고리즘을 적용했다. 

이런식으로.. 헷갈리면 직접 그림을 그리고 계산해보면 금방 이해될거라고 생각한다.