[백준]1011. Fly me to the Alpha Centauri (java, python)

링크

Fly me to the Alpha Centauri

문제 분석

풀이 1(java)

문제의 핵심은 거리 값이 좌우 대칭이 된다는 것입니다

처음과 끝은 1이 되어야하므로 1 1 2 2 3 3 4 4 ... 이렇게 더해나가다가 전체 거리를 초과한다면 최소 작동 횟수를 얻을 수 있습니다

풀이 2(python)

규칙 하나를 깨닫는다면 짧은 코드로 풀 수 있습니다

2^2 = 1 + 2 + 1

3^2 = 1 + 2 + 3 + 2 + 1

4^2 = 1 + 2 + 3 + 4 + 3 + 2 + 1

코드

JAVA

import java.util.Scanner;

public class Q1011 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();

        while(tc-- > 0) {
            int x = sc.nextInt();
            int y = sc.nextInt();

            long dist = 0, i = 1;
            while(dist < y - x)
                dist += (i++ + 1) / 2;

            System.out.println(i - 1);
        }
    }
}

PYTHON

import math
for _ in range(int(input())):
    x, y = map(int, input().split())
    print(math.ceil(2 * math.sqrt(y - x) - 1))