[BOJ] 1011. Fly me to the Alpha Centauri

문제 원본 : https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        ArrayList<Long> preCalc = new ArrayList<>();
        for (long i = 0; ; ++i) {
            preCalc.add(i * i + i * 3);

            if (i * i + i * 3 > Integer.MAX_VALUE) {
                break;
            }
        }

        for (int i = 0; i < n; ++i) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();

            if (y - x < 3) {
                System.out.println(y - x);
                continue;
            }

            for (int j = 1; j < preCalc.size(); ++j) {
                if (preCalc.get(j - 1) + 2 < y - x && y - x <= preCalc.get(j) + 2) {
                    if ((preCalc.get(j - 1) + 2 + preCalc.get(j) + 2) / 2 < y - x) {
                        System.out.println(4 + 2 * (j - 1));
                    } else {
                        System.out.println(3 + 2 * (j - 1));
                    }
                    break;
                }
            }
        }
    }
}

• 규칙은 간단한데 일반항을 찾다가 포기...
• 1 2 3 3 4 4 5 5 5 6 6 6 7 7 7 7 8 8 8 8
• 그렇다 보니 시간이 엄청 오래 걸리고 메모리 사용량이 엄청 높다.
• 다른 사람들 풀이를 보니 제곱수마다 규칙이 있는 것을 깨달았다...
• 수학 공부 좀 하자.