[java] 백준 알고리즘 1011번 Fly me to the Alpha Centauri 풀이

노가다겠지만, 

거리가 1~25까지 최소 작동 회수를 구해보면 좋을 듯 싶다.

종이에 옮겨놓으면 그나마 이해가 될 때가 많다.

0~1, 0~2, 0~3, 0~4 쭉쭉 최소 작동 회수를 구해본다.

0에서 해도 되는 이유는 결국 거리를 얼만큼 최소로 이동하느냐기 때문에

45~50이 입력되든 0~5가 입력되든 거리는 5라서 상관이 없다.

쭉쭉 구하다보면 완벽한 데칼코마니가 되는 순간 이후부터 최소 작동회수가 올라간다.

예시)

0에서 1(총 1번): 1

0에서 2(총 2번): 11

0에서 3(총 3번): 111

0에서 4(총 3번): 121

0에서 5(총 4번): 1211

0에서 6(총 4번): 1221

0에서 7(총 5번): 12211

.

.

.

.(중략)

.

0에서 12(총 6번): 123321

0에서 13(총 7번): 1233211

.

.

.

0에서 20(총 8번): 12344321

0에서 21(총 9번): 123443211

서서히 빨라졌다 서서히 느려지는게 최소횟수가 되는 것이다.

그 외에는 대충 끼워넣기 느낌 밖에 들지 않는다

데칼코마니를 찾기 위해

앞에서 부터 그리고 뒤에서 부터 숫자를 더해주고 빼준다.

그와 동시에 작동한 횟수를 ++ 해준다

완벽한 데칼코마니 혹은 x쪽에서 데칼코마니를 넘었을 땐 break

x가 움직인 후 y쪽에서 완벽한 데칼코마니를 넘었을 땐 거기서 break

* 풀이 소스

public class Baekjoon1011 {
 
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        
        int t = Integer.parseInt(st.nextToken());
        for(int i=0; i<t; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int movingDistance = 0;
            int xMovingCount = 0;
            int yMovingCount = 0;
            
            while(true) {
                movingDistance++;
                
                x += movingDistance;
                xMovingCount++; // x의 이동횟수
                
                if(x >= y) {
                    break;
                }
                
                y -= movingDistance;
                yMovingCount++; // y의 
                if(y <= x) {
                    break;
                }
                
            }
            bw.write(String.valueOf(xMovingCount+yMovingCount));
            bw.newLine();
        }
        bw.flush();
    }
 
}