백준알고리즘 #1011 Fly me to the Alpha Centauri java

백준알고리즘 #1011 Fly me to the Alpha Centauri 문제

 

백준알고리즘 #1011 Fly me to the Alpha Centauri 문제2

 

시간이 굉장히 많이 걸렸던 문제이다.

 먼저 거리가 1부터 차례대로 증가할 때마다 다음과 같이 이동하는 것이 최소값이라는것을 확인한다.

거리별 작동횟수 및 방법

위의 규칙에 따르면 4, 9, 16처럼 제곱수 마다 횟수가 1씩 증가하는 것을 알 수 있는데 이 때 거리가 x^2일때 이동횟수가 x+(x-1)이라는 것을 알 수 있다.

다만 (x-1)^2 과 x^2 사이에 작동횟수가 한번 증가하는 구간이 있는데 이 구간은 x^2 - (x-1)^2 의 중간값이므로 몫을 구하는 / 연산자를 이용하여 계산해준다.

함수 설정

위의 조건에 따라 함수를 작성한 것이다.

처음 설정을 int로 해 두는 바람에 시간 초과라는 에러 표시가 발생했다. 

만약 변수를 int로 설정할 경우 거리 dis 보다 큰 제곱수 i 를 찾을 때 오버플로우가 발생해버리게 된다. 

따라서 변수를 long으로 설정할 것.

메인

main함수에서 테스트케이스와 x,y 값을 입력받고 각 테스트케이스를 출력하는 코드

(입력받는 x와 y값은 범위가 2^31로 한정되어있으므로 int로 해도 무방하지만 모두 long으로 설정하였다.)