BOJ 1011 - Fly me to the Alpha Centauri

문제

우주선이 x에서 y로 이동할 때, 매 단계 이동거리를 이전 대비 -1, 0, +1만 변경 가능하고, 출발과 도착 시 이동거리가 1이어야 한다. 최소 이동 횟수를 구하라.

입력

첫째 줄에 T, 이후 T줄에 x와 y가 주어진다.

출력

각 케이스마다 최소 이동 횟수를 출력한다.

예제

입력	출력
`3` `0 3` `1 5` `45 50`	`3` `3` `4`

풀이

이동거리가 1, 2, ..., k, ..., 2, 1 형태일 때 총 거리가 k²임을 이용하여 수학적으로 계산한다.

거리 d = y - x를 구한다
k = floor(sqrt(d))를 구한다
d == k²이면 답은 2k - 1 (대칭 이동)
d가 k*(k+1) 이하이면 답은 2k (한쪽만 연장)
그 외이면 답은 2k + 1

핵심 아이디어: 최적 이동 패턴은 1, 2, ..., k, ..., 2, 1로 총 이동거리가 k²이며, 이를 기준으로 초과분에 따라 횟수를 결정한다.

코드

package day649;
 
import java.io.*;
 
public class Day619BOJ1011플라이알파 {
  public static void main(String[] args) throws Exception {
    BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    for (int n = Integer.parseInt(re.readLine()); n > 0; n--) {
      String[] input = re.readLine().split(" ");
      int distance = Integer.parseInt(input[1]) - Integer.parseInt(input[0]);
      int maxDiff = (int) Math.sqrt(distance);
      if (distance == maxDiff * maxDiff) {
        sb.append(maxDiff * 2 - 1);
      } else if (distance <= maxDiff * (maxDiff + 1)) {
        sb.append(maxDiff * 2);
      } else {
        sb.append(maxDiff * 2 + 1);
      }
      sb.append('\n');
    }
    System.out.println(sb);
  }
}

복잡도

시간: O(T) - 각 테스트 케이스 O(1)
공간: O(1)

문제

BOJ 1011 - Fly me to the Alpha Centauri

입력

첫째 줄에 T, 이후 T줄에 x와 y가 주어진다.

출력

각 케이스마다 최소 이동 횟수를 출력한다.

예제

입력	출력
`3` `0 3` `1 5` `45 50`	`3` `3` `4`

풀이

이동거리가 1, 2, ..., k, ..., 2, 1 형태일 때 총 거리가 k²임을 이용하여 수학적으로 계산한다.

거리 d = y - x를 구한다
k = floor(sqrt(d))를 구한다
d == k²이면 답은 2k - 1 (대칭 이동)
d가 k*(k+1) 이하이면 답은 2k (한쪽만 연장)
그 외이면 답은 2k + 1

핵심 아이디어: 최적 이동 패턴은 1, 2, ..., k, ..., 2, 1로 총 이동거리가 k²이며, 이를 기준으로 초과분에 따라 횟수를 결정한다.

코드

package day649;
 
import java.io.*;
 
public class Day619BOJ1011플라이알파 {
  public static void main(String[] args) throws Exception {
    BufferedReader re = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    for (int n = Integer.parseInt(re.readLine()); n > 0; n--) {
      String[] input = re.readLine().split(" ");
      int distance = Integer.parseInt(input[1]) - Integer.parseInt(input[0]);
      int maxDiff = (int) Math.sqrt(distance);
      if (distance == maxDiff * maxDiff) {
        sb.append(maxDiff * 2 - 1);
      } else if (distance <= maxDiff * (maxDiff + 1)) {
        sb.append(maxDiff * 2);
      } else {
        sb.append(maxDiff * 2 + 1);
      }
      sb.append('\n');
    }
    System.out.println(sb);
  }
}

복잡도

시간: O(T) - 각 테스트 케이스 O(1)
공간: O(1)