규칙성 찾기

source: https://www.acmicpc.net/problem/1011
ref: https://cocoon1787.tistory.com/622

x지점부터 정확히 y지점으로 이동하는데 필요한 공간 이동 장치 작동 횟수의 최솟값을 구하는 프로그램을 작성하라.

규칙 찾으려는 노력(?)이 부족해서 헤맸던 문제.

규칙을 찾기 위해 다음과 같이 이동거리별로 작동횟수를 세어 본다.

이동거리별 작동횟수를 나열하여 다음과 같은 규칙을 찾으려 노력한다.

찾은 규칙을 코드로 옮긴다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	 public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
		int count = 0;
		for (int i = 0; i < T; i++) {
	
			String input = br.readLine();
            String[] result = input.split(" ");
            int x = Integer.parseInt(result[0]);
            int y = Integer.parseInt(result[1]);
			int d = y - x;
			int rd = (int)Math.sqrt(d); 
			
			if(d == rd*rd) {
                count = 2*rd-1;
				System.out.println(count);
			}else if(d <= rd + rd*rd){
                count = 2*rd;
				System.out.println(count);
			} else {
                count = 2*rd+1;
				System.out.println(count);
			}
		}

	}
}

문제에서 나열하면 규칙성이 반드시 있다고 힌트가 주어졌다면 규칙을 찾기 위해 조금 더 노력했을 것 같다.