BOJ #1011 Fly me to the Alpha Centauri

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.

문제 링크

문제 1011. Fly me to the Alpha Centauri

1번 풀이

문제만 봤을 땐 풀이가 그닥 잘 떠오르지 않는다. 다만 지문에서도 나와있듯이 $k_=k_n-1\ or\ k_n\ or\ k_n + 1$로 갈 수 있고 각 거리에 대해 최소 가동횟수 1개의 값만을 가지므로 수열의 형태로 표현할 수 있겠다. 1부터 각 거리에 대해 횟수를 구해보면 다음 그림과 같다.

일정 구간에 대해 횟수가 동일함을 볼 수 있으므로 주어진 거리가 어디에 속하는지 알 수 있다면 작동 횟수도 알 수 있다.

기계의 작동 횟수	시작 거리
1	1
2	2
3	3
4	5
5	7
6	10

위의 규칙을 보면 작동 횟수에 n에 대해 시작 거리를 $a_n$이라 하면 $a_{n+1}=a_n+\lceil \cfrac{n}{2}\rceil$($\lceil\rceil$: 올림)의 규칙을 확인할 수 있다. 즉, 반복문으로 더해가면서 주어진 거리 n에 대해 $a_n \le x \le a_{n+1}$의 범위를 특정하면 해답을 구할 수 있고 시작복잡도는 $O(\sqrt n)$이 된다.

python 코드

import math
import sys
 
N = int(sys.stdin.readline()) # 케이스의 수
for _ in range(N): # 각 케이스에 대해
    x, y = map(int, sys.stdin.readline().split()) # 좌표 값 입력
    v = y - x # 주어진 좌표 간 거리
    a = 1 # 첫번째 항
    i = 1 # 첫번째 작동
    while a < v: # 아직 끝까지 도달하지 못했다면
        a += math.ceil(i / 2) # 
        if a > v:
            break
        i += 1
    print(i)

2번 풀이

뭔가 오래 걸린다. 문제의 시간 제한이 2초인데 1.7초라는 시간이 소요되었다는 사실은 굉장히 찝찝하다. 수학적 풀이를 찾아보자.

가장 이상적인 작동형태는 $1\ \dots\ n-1,\ n,\ n-1\ \dots\ 1$로 보인다. 즉, 대칭을 의미하고 절반으로 나눴을 때 $\cfrac{k(k+1)}{2}$의 모양이다. 이쯤되면 작동거리가 제곱수일 때 규칙성을 찾을 가능성이 얼핏 보인다. 제곱수 $k^2$에 대해 작동횟수는 일관되게 $2k-1$임을 알 수 있고 $k^2$과 $(k+1)^2$항을 제외하면 그 사이에는 $2k$개의 항이 존재한다. (∵ $(k+1)^2 - k^2 - 1$) 그리고 $2k$의 항에 대해 정확히 $k$개로 2등분되고 있음을 확인할 수 있으므로 제곱수, 제곱수 + k, 제곱수 + 2k의 세개 범위로 모든 항을 판별할 수 있다.

python 코드

import sys
 
N = int(sys.stdin.readline()) # 케이스의 수
for _ in range(N): # 각 케이스에 대해
    x, y = map(int, sys.stdin.readline().split()) # 좌표 값 입력
    v = y - x # 주어진 좌표 간 거리
    n = int(v ** 0.5) # 제곱근 내림
    a = v - n ** 2 # v - n^2하여 나머지 수 구하기
    if a == 0: # 제곱수라면
        print(2 * n - 1) # 2n - 1
    elif 0 < a <= n: # 제곱수 + n까지의 범위라면
        print(2 * n) # 2n
    else: # 제곱수 + n + 1에서 다음 제곱수 전까지
        print(2 * n + 1) # 2n +  1