[Python] 백준1011. Fly me to the Alpha Centauri

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

문제 설명

x -> y까지 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.

예를 들어 0,3 까지 가기 위해서 1,1,1 총 3번의 공간이동이 필요하다.

 

여기서 주의할 점이 몇가지 있다.

• 시작할때와 도착하기전에는 무조건 1광년만 이동이 가능하다.
• 처음 작동시킬 경우 -1 0 1 만큼만 이동이 가능하다. 
  • 그 다음으로 0 1 2 광년을 이동 할 수 있다.
  • 그 다음 2광년 이동한다면 다음 이동가능한 광년은 1 2 3 이다
• 그렇다면 거리가 11이라면 어떻게 이동해야할까?
  • 1,2,3,4,1 이렇게는 이동 불가능하다.
  • 1,2,3,2,2,1 으로 이동이 가능하다.
    • 처음 1광년만 이동이 가능하다 -> 남은 거리 10
    • (남은 거리 10) 1광년 이동했다면 다음으로는 0,1,2 이동 가능하다 (2 선택) 10-2
    • (남은 거리 8) 2광년 이동했다면 다음으로는 1,2,3 이동 가능하다 (3 선택) 8-3
    • (남은 거리 5) 3광년 이동했다면 다음으로 2,3,4 이동 가능하다 (4 선택) -> 5-4
    • (남은 거리 1 ) 4광년 이동했다면 다음으로 3,4,5 이동 가능하다.
      • 마지막은 1광년만 이동이 가능하다 
        • 4를 선택하면 다음도 3,4,5 거리만 이동 가능하다. -> 이동이 불가하다.
        • 3을 선택하면 다음 움직일 수 있는거리는 2,3,4 이다.  -> 이동이 불가하다.
        • 숫자를 줄여야 한다.
    • 다시 남은 거리 5로 돌아가보자 4가 아닌 2를 선택한다. (2 선택) 5-2
    • (남은 거리 3) 2광년 이동했다면 다음으로 1,2,3 이동가능하다. (2선택) 3-2
    • (남은 거리 1) 거리가 1이 남았으며 마지막은 1광년만 이동가능하다에 적합하다.

 

표로 다시 정리해보자 거리가 1부터 16까지 정리해보았다.

Distance와 max의 관계

Distance	move	Count	max
1	1	1	1
2	11	2	1
3	111	3	1
4	121	3	2
5	1211	4	2
6	1221	4	2
7	12211	5	2
8	12221	5	2
9	12321	5	3
10	123211	6	3
11	123221	6	3
12	123321	6	3
13	1233211	7	3
14	1233221	7	3
15	1233321	7	3
16	1234321	7	4

여기서 주목할점은 파란색 부분이다.

Distance 4 일때 max = 2가 된다.

Distance 9 일때 max = 3이 된다.

Distance 16 일때 max = 4가 된다.

 

어떤게 떠오르지 않는가? 루트이다. 16의 루트는 = 4가 된다. 

그렇다면 Distance 25면 max = 5가 되는 것이다.

 

Code

max = int(math.sqrt(distance))
    if max == math.sqrt(distance):
        print(2 * max -1)

---

cnt 변화

Distance	Count	max
1	1	1
2	2	1
3	3	1
4	3	2
5	4	2
6	4	2
7	5	2
8	5	2
9	5	3
10	6	3
11	6	3
12	6	3
13	7	3
14	7	3
15	7	3
16	7	4

• 규칙1 : max가 1씩 증가할때마다 cnt의 값이 두번씩 바뀌고 있다.
• 규칙2 : max가 1씩 증가할때 cnt의 값이 변한다.
  • max 값이 변할 때는 cnt는 다음 공식을 만들 수 있다.
    • cnt = (max * 2) -1
    • max = 3일때 cnt 5가 된다.
    • max = 4일때 cnt 7이 된다.
• 규칙3 : max의 값만큼 cnt가 반복된다.
  • cnt가 4에서 5로 될때 2번만에 값이 바뀐다.
  • cnt가 6에서 7로 될때 3번만에 값이 바뀐다.

10~12(max * max < distance <= max * max + max) 까지 cnt는 2 * max가 된다.

13~15 까지 cnt는 2 * max + 1이 된다.

 

Code

    elif distance <= (max * max + max):
        print(2 * max)
    else:
        print(2 * max+1)

 

 

---

전체코드

import math
import sys

input = sys.stdin.readline

def fun2(distance):
    max = int(math.sqrt(distance))
    if max == math.sqrt(distance):
        print(2 * max -1)
    elif distance <= (max * max + max):
        print(2 * max)
    else:
        print(2 * max+1)
    return


T = int(input())
for case in range(T):
    x, y = map(int, input().split())
    fun2(y-x)

 

 

Reference

---

https://st-lab.tistory.com/79