백준 1011번 풀이

문제

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

1011번: Fly me to the Alpha Centauri

시발점 A와 종점 B가 주어질 때, 해당 거리를 이동하기 위해 공간이동장치의 최소 작동횟수 구하기. (직접 가서 보는 걸 추천드림)

 

Reference

https://data-jj.tistory.com/36

백준 1011번 풀이(파이썬)

 

풀이

솔직히 패턴 찾다가 뇌정지 왔음… 그건 둘째치고 광년거리면 가다가 늙을 거 같은데 장치에 -1이랑 0 있는 건 누르면 욕 바가지로 먹을 수 있다 뭐 그래요 알파 센타우리… 가야된다는데 어쩌겠음… 근데 가다가 블랙홀 만나면 X되는겨 조심해… 블랙홀은 육안으로 보이지도 않아요…

참고문헌 들어갔더니 패턴을 이렇게 정리해두셨다… 와 진짜 존경…

 

저기서는 크게 네 가지 패턴으로 나눴는데

1. 거리 < 4
2. 거리 = 제곱수
3. 거리 <= 제곱수+루트 제곱수
4. 거리 > 제곱수+루트 제곱수

이렇게 네 가지로 나눴다.

 

거리가 4일 때는 작동횟수가 곧 거리이므로 패스하고 세 가지 구간에 대해서만 보고 갑시다. 일단 저기 두번째 줄에 4, 5, 6, 7, 8을 순서대로 보자. 4는 제곱수, 5와 6은 작거나 같은 구간, 7, 8은 큰 구간이다. 그러니까 6을 경계로 구간이 두 개인 셈. 9 아래로는 12를 기준으로 나눈다. 그럼 16은? 아마 20일듯… 16+4는 20이니까.

 

거리가 제곱수일 때 작동 횟수는 4일때 3, 9일때 5, 16일때 7이다. 제곱수가 n^2형태이니까 n^2로 놓고 보면 2의 2승일때 3, 3의 2승일때 5, 4의 2승일때 7인데… 그렇다. 제곱수일 때의 작동 형태는 2n-1의 형태이다. 그럼 남는건 언더랑 클 때인데… 6보다 작거나 같을 때는 작동횟수가 4이고, 6보다 클 때는 5이다. 그리고 12보다 작거나 같을 때는 작동횟수가 6, 클때는 7이다. 2^2+2보다 작거나 같을 때 4이고, 2^2+2보다 클 때 5이다. 즉 거리가 제곱수+루트 제곱수보다 작거나 같을 때 작동횟수는 2n이고, 클 때는 2n+1이다.

import sys
case = int(sys.stdin.readline())
# 입력
for i in range(case):
    start,end = map(int,sys.stdin.readline().split())
    count = 0 # 이동 횟수
    distance = end - start # 시종점간 거리(대충 가야 하는 거리) 
    move_max = int(distance ** 0.5) # 네? 루트요? 0.5승 하면 되잖아요! 
    square = move_max ** 2 # 제(별)곱 아 급 곱창떙기네... 
    if distance == square:
        count = move_max * 2 - 1
        # 제곱수
    elif distance <= square + move_max:
        count = move_max * 2
        # 제곱수+루트보다 같거나 작은 구간
    elif distance > square + move_max: 
        count = move_max * 2 + 1
        # 제곱수+루트보다 큰 구간
    elif distance < 4: 
        count = distance
        # 4보다 작을 때
    print(count)

이거 말고 다른 패턴으로 하는 방법도 있긴 있는데, 본인은 저 방법이 제일 확 와닿았음…