[백준 알고리즘] 1011 - Fly me to the Alpha Centauri

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

1011번: Fly me to the Alpha Centauri

 

이 문제의 경우 직접 종이에 써가면서 규칙을 찾는 것이 중요합니다. 단순하게 규칙을 찾아서 적용한 풀이를 설명할 것이며 어떠한 식을 구해서 푸는 방법도 있으니 참고하시기 바랍니다.

 

먼저 작동횟수를 기준으로 어떤 방식으로 이동하는지 확인해보겠습니다.

 

 

위 그림을 보면 서서히 이동거리를 증가시켰다가 서서히 이동거리를 감소시키는 방법이 최단거리임을 알 수 있습니다.

 

오른쪽과 왼쪽의 숫자가 최대한 같아질 수 있도록 하기 위해 앞에서 한번, 뒤에서 한번 숫자를 더하고 빼주는 작업을 반복합니다. 그와 동시에 작동 횟수를 증가시킵니다.

 

완벽한 데칼코마니를 이룬 경우 또는 x(왼쪽 지점)과 y(오른쪽 지점)이 교차된 경우 반복을 종료하고 지금까지 양쪽에서 이동했던 횟수를 더해 출력합니다.

 

자바 코드는 다음과 같습니다.

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            String[] inputs = br.readLine().split(" ");
            int x = Integer.parseInt(inputs[0]);
            int y = Integer.parseInt(inputs[1]);

            int movingDistance = 0;
            int xMovingDistance = 0;
            int yMovingDistance = 0;

            while (true) {
                movingDistance++;

                x += movingDistance;
                xMovingDistance++;  // x의 이동 횟수

                if (x >= y) {
                    break;
                }

                y -= movingDistance;
                yMovingDistance++;  // y의 이동 횟수

                if (x >= y) {
                    break;
                }
            }

            bw.write(String.valueOf(xMovingDistance + yMovingDistance));
            bw.newLine();
        }

        bw.flush();
    }
}

 

위 풀이는 아래 글을 참고하였습니다.

- https://zorba91.tistory.com/116

 

규칙과 식을 만들어 푸는 방법은 아래 글을 참고하시면 좋을 것 같습니다.

- https://st-lab.tistory.com/79