[백준] 1011 Fly me to the Alpha Centauri 파이썬 풀이 (기본 수학 1)

 

코드

 

num = int(input()) #몇 번 케이스 돌건지
count = 0
for i in range(num):
    x,y = map(int, input().split())
    distance = y-x
    k = distance ** 0.5 #제곱근 구하기
    k = int(k) #제곱근을 int로 바꿈
    count = 0  #횟수
    if distance == k*k: 
        count = 2*k-1
    elif distance >k*k and distance <= k*(k+1):
        count = 2*k
    elif distance > k*(k+1) and distance <= k*(k+2):
        count= 2*k+1
    print(count)
 
 

 

문제풀이

 

거리가 1일때부터 10일때까지만 살펴보자

1일때는 거리 1로 한번 가면 된다

2일때는 거리 1로 2번 갈 수 있다.

3일때는 거리 1로 3번 갈 수 있다.

왜냐????????????????????

처음이랑 마지막은 꼭 1만 가라고 했으니까!

 

4일때는 거리 1 2 1 로 가야 젤 빨리 가는것이다.

1 1 1 1 로 갈 수도 있겠지만 그것은 느리다.

거리를 계산 하는 순서는 좌우 대칭으로 그림을 그려본다

맨 앞에 1을 갔으면 맨 뒤에 1을 가보고 앞에서 2를 갔으면 뒤에서도 2를 가보고 이렇게!

아무튼

5일때 맨앞에서 1을 가고 맨 뒤에서 1을 가고 또 앞으로 돌아와서 2를 가고 다시 뒤로 돌아가서 2를 가려고 하는데!

1밖에 안남아서 1만 간다

6일때는 1 2 2 1 로 대칭으로 간다

7일때는 6처럼 대칭으로 가는데 중간에 1이 남아서 1한번을 더간다

8일때는 1 2 2 2 1 로 대칭으로 간다

9일때는 1 2 3 2 1 로 대칭으로 간다

---

여기서 볼 수 있는 점!

4와 9는 딱 예쁜 대칭이 된다

1 2 1 / 1 2 3 2 1

이렇게 된다는 것이다.

왜인지 보자면

거리들을 다 더하면 4와 9가 된다.

1+2+1 은 4가 되고 1+2+3+2+1 은 9가 된다.

그러면 16은? 1+2+3+4+3+2+1 이 된다.

예쁜 대칭이 된다는 것이다!!!!

그것은 언제 일어나는 일이냐!

총 거리가 n의 제곱일때 일어난다 (n은 최고 높이)

16으로 치면 최고 높이가 4인데 최고 높이의 제곱이 16이 된다.

그럼 거리가 자연수n의 제곱이면 그때 최소한으로 가는 공간이동 작동 횟수는

n+(n-1)이다.

1+2+3+2+1 여기서 더하기해주는 숫자의 수의 개수를 수식으로 표현하면 이렇게 됨

3+2개 니까

 

그런데 거리가 자연수n의 제곱과 n+1의 제곱 사이에는 어떤 일이 일어나는가

예를 들어 2의 제곱인 4와 3의 제곱인 9 사이의 수들

5 6 7 8은 또 다른 횟수를 수식으로 적용시켜 줘야한다는 것이다.

4와 9사이의 거리에서 최고 속도는 2여야한다.

(9가 되는 순간 최고 속도가 3이 최초로 되기 때문)

그래서 4보다 거리가 3 더해진 7이 나왔을때는 속도를 높여서 3 속도로 가면 안되고

1+2 이렇게 나누어서 가야한다는 것이다.

이말은 최고 속도가 n이라고 했을때

거리가 n제곱 + n 이하이면 / 거리가 n제곱일때의 횟수 +1만 하면되고

거리가 n제곱 + n보다 크고 n제곱 + 2n 이하 이면 / 거리가 n제곱일때의 횟수 +2를 하면 된다는 것이다.

 

---

거리는 y-x이므로

거리의 제곱근을 구한다.

그리고 int로 바꿔준다

4는 2가 나올것이고 9가 되기전까지 자연수들은 다 2가 나올 것이고

9부터 15까지는 3이 나올것이고... 이렇게 나올 것이다

 

위에서 설명한 그대로

거리가 제곱근(k)의 제곱이면 k+(k-1) 이 횟수이고

거리가 k의 제곱보다 크고 k의 제곱 + k보다 작거나 같으면 k+(k-1)+1이 횟수이고

거리가 k의 제곱  +k보다 크고 k의 제곱 + 2k보다 작거나 같으면 k+(k-1)+2이 횟수이다.