[백준 17613] 2019 정올 1차 고등부 "점프"

문제 출처 : https://www.acmicpc.net/problem/17613

17613번: 점프

이 문제는 2019년 정보올림피아드 1차 고등부 2번 문제 입니다.

점프를 하면서 해당 위치에 갈 수 있는 가장 짧은 점프 횟수를 찾는 문제 입니다. 여기 까지는 쉽지만 범위 안에 있는 모든 짧은 점프 횟수를 찾아 그중 가장 큰 수를 출력해야 합니다.

문제 이해하기

예제 입력에 있는 3번째 경우를 보겠습니다. 12부터 16사이에 가장 큰 점프 횟수를 찾아야 합니다.

먼저 12에 도달하는 점프넘버를 생각해 보겠습니다. 1칸을 점프하면 빨간색, 2칸은 주황색, 4칸은 노란색으로 표현하였습니다. 무지개의 빨, 주, 노, 초, 파, 남, 보 순으로 생각하면 됩니다. 4칸인 노란색에서 다음번 숫자인 8칸을 점프하면 15가 되기 때문에 처음으로 돌아와 1칸을 뛴 것입니다. 다음 2칸 뒤에 또 4칸을 뛰면 14가 되기 때문에 다시 1칸, 또 1칸을 점프하여 총 7번의 점프로 12에 도달한 것입니다.

13까지 역시 마지막에 주황색인 2칸 점프로 7번에 만들 수 있습니다.

14까지는 마지막에 4칸 점프로 6번만에 만들 수 있습니다.

15까지는 8칸 점프를 사용해 4번만에 도달할 수 있습니다. 마지막 16은 1칸 점프로 돌아와 5번 만에 도달할 수 있습니다.

이렇게 모든 점프넘버를 구한 뒤 가장 큰 숫자인 7을 출력하면 됩니다.

여기까지 보면서 알 수 있는 사실이 몇가지 있습니다. 첫 번째로 각 점프넘버의 시작이 되는 숫자가 2의 제곱수에서 1을 뺀 숫자라는 것입니다. 아래와 같이 처음부터 점프넘버가 될 숫자들은 나타낼 수 있습니다.

1 : 2 ** 1 - 1 3 : 2 ** 2 - 1 7 : 2 ** 3 - 1 15 : 2 ** 4 - 1

 

두 번째로 알 수 있는 것은 최대한 멀리 뛰어주는 것이 최소값을 구할 수 있습니다. 점프 한 번 더하면 2배씩 거리가 늘기 때문에 최대한 멀리 뛰어주어야 합니다.

세 번째로 점프 거리를 초기화 하면 이전에 만들었던 점프은 규칙으로 점프한다는 것 입니다. 위에서 14를 보면 7까지 이동한 3회와 똑같은 3회 점프로 총 6을 얻었습니다.

즉 14의 점프 넘버를 찾는 방법은 최대로 일단 점프를 하여 7이라는 위치에 도착합니다. 한 번 더 뛰면 15에 도착하기 때문에 다시 1칸부터 뜁니다. 즉 7에서 14까지는 1에서 0에서 6까지의 점프넘버에서 7까지의 점프 넘버 3을 더해준 것과 같습니다. 마찬가지로 15에서 31까지는 0에서 14까지의 점프넘버에 4를 더한 것과 같습니다. 이것을 식으로 나타내면 아래와 같습니다.

• J(2 ** n - 1) = n + J(2 ** (n - 1) - 1)

식의 모양만 보면 DP로 만들면 좋겠지만 수의 범위가 10억입니다. 거기다 범위가 두배씩 커지기 때문에 DP보다는 그냥 재귀 함수로 만드는 것이 효율적 입니다.

알고리즘

그럼 우리가 위에서 알게된 사실을 가지고 규칙을 만들어 보겠습니다.

1. 최대한 멀리 뜁니다. 다음 점프에서 값이 너머가지 않을 때까지 점프넘버를 구합니다.
2. 위에서 구한 점프넘버를 전체 범위에서 빼주어 계산합니다.
3. 같은 방식으로 줄어드는 범위의 점프넘버를 반복적으로 구해줍니다.
4. 점프넘버의 최대값을 출력해 줍니다.

코드 작성하기

위에서 알아본 규칙을 가지고 코드를 작성해 보겠습니다.

입력 받기

T = int(input())

for _ in range(T):
    x, y = map(int, input().split())
    print(solve(x, y))

먼저 테스트 케이스 T를 입력 받습니다. 그 뒤 T번 만큼 범위 x, y를 입력 받습니다. 그리고 solve라는 함수를 사용하여 x, y 범위의 최대값을 출력합니다.

인덱스 찾기

점프는 2의 배수로 진행이 됩니다. 2의 32승이 21억정도니까 32번 반복안에 가장 멀리 점프하는 거리를 찾을 수 있습니다.

arr = [0]
for i in range(1, 32):
    arr.append((1 << i) - 1)

def get_idx(n):
    for i in range(32):
        if n < arr[i + 1]:
            return i

arr은 점프 넘버를 기억하는 리스트 입니다. 앞에서 구한 0, 1, 3, 7, 15 … 의 값이 들어 있습니다. arr[i + 1]이 n의 값을 넘는 첫 번째 수이기 때문에 i는 n의 값을 넘지 않는 마지막 점프 넘버가 됩니다.

점프 함수

def jump(num):
    if num <= 1:
        return num
    
    idx = get_idx(num)    
    return jump(num - arr[idx]) + idx

점프 넘버가 0일때는 0, 1일때는 1을 리턴합니다. 그 외에는 앞서 구했던 점화식을 통해 점프 넘버를 구합니다.

• J(2 ** n - 1) = n + J(2 ** (n - 1) - 1)

이 점화식을 식으로 나타내면 아래와 같습니다.

• jump(n) = jump(n - arr[i]) + i

이 때 i는 n을 넘지 않는 최대의 점프넘버 입니다.

solve 함수

def solve(start, end):
    if end == start:
        return jump(start)
    if end - start == 1:
        return max(jump(start), jump(end))
    
    idx = get_idx(end)
    if start < arr[idx]:
        case1 = solve(0, end - arr[idx]) + idx     
        case2 = solve(max(0, start - arr[idx - 1]), arr[idx - 1]) + idx - 1
        return max(case1, case2)
    elif start == arr[idx]:
        return solve(0, end - arr[idx]) + idx
    else:
        return solve(start - arr[idx], end - arr[idx]) + idx

solve 함수는 범위 내 가장 큰 점프 넘버를 찾는 것입니다. 우리는 점프를 했을 때 범위를 줄이는 방법을 알고 있습니다. jump(n) = jump(n - arr[i]) + i 식을 통해 최대한 범위를 줄여 나가야 합니다. 이 식을 사용하기 위해서 범위를 생각해 보겠습니다. 먼저 get_idx를 통해 최대한 멀리 뛴 점프 넘버를 구해 줍니다. 그렇게 구한 값이 idx 입니다.

먼저 idx를 구한 값이 start 보다 작은 경우 입니다. 이 경우는 범위를 계산할 필요가 없습니다. 범위를 줄여주는 것으로 합니다. 그것이 맨 마지막 return 문에 있는 부분 입니다.

return solve(start - arr[idx], end - arr[idx]) + idx

다음으로 idx의 범위가 start와 같을 경우 입니다.

이 경우는 범위를 idx만큼 빼주면 됩니다.

return solve(0, end - arr[idx]) + idx

이제 idx의 범위를 고려할 부분은 start와 end의 사이에 있는 경우 입니다.

이 부분은 두 부분으로 나누어 생각해야 합니다.

ans = max(solve(start, idx - 1), solve(idx, end))

이렇게 나눌 수 있습니다. 뒤쪽의 solve(idx, end) 는 위에서 했던 식 solve(0, end -arr[i]) + i로 나타낼 수 있다고 하였습니다. 앞쪽 solve(start, idx)는 arr[idx - 1]을 사용해 위에서 했던 범위 그대로 나눌 수 있습니다.

start의 위치는 start - arr[i - 1]이 됩니다. 문제는 이 값이 0 보다 작아질 수 있습니다. 따라서 max(0, start - arr[i - 1])로 하였습니다. 다음으로 idx - 1의 위치는 결국 arr[i - 1]과 같습니다. idx 위치는 arr[i]로 나타낼 수 있고, 결국 idx - arr[i - 1] - 1은 arr[i] - arr[i - 1] - 1이 됩니다. 이 값은 arr[i - 1]과 같은 것입니다.

idx의 위치를 생각하면 쉽게 이해할 수 있습니다. 1, 3, 7, 15로 2 ** n - 1의 형태로 커지기 때문 입니다. 15를 예를 들면 15 - 7 - 1 은 7이 됩니다. 7 - 3 - 1 역시 3이 됩니다. 2배씩 커지는 것을 이해하면 쉽게 알 수 있습니다.ㄱ

전체 코드

T = int(input())

arr = [0]
for i in range(1, 32):
    arr.append((1 << i) - 1)

def get_idx(n):
    for i in range(32):
        if n < arr[i + 1]:
            return i

def jump(num):
    if num <= 1:
        return num
    
    idx = get_idx(num)    
    return jump(num - arr[idx]) + idx

def solve(start, end):
    if end == start:
        return jump(start)
    if end - start == 1:
        return max(jump(start), jump(end))
    
    idx = get_idx(end)
    if start < arr[idx]:
        case1 = solve(0, end - arr[idx]) + idx     
        case2 = solve(max(0, start - arr[idx - 1]), arr[idx - 1]) + idx - 1
        return max(case1, case2)
    elif start == arr[idx]:
        return solve(0, end - arr[idx]) + idx
    else:
        return solve(start - arr[idx], end - arr[idx]) + idx
        

for _ in range(T):
    x, y = map(int, input().split())
    print(solve(x, y))