AtCoder: ABC 180 D

atcoder.jp/contests/abc180/tasks/abc180_d

D - Takahashi Unevolved

곱셈과 덧셈을 통해서 숫자를 키워줄 수 있고, 상한선을 넘지 않는 한에서 가장 많은 횟수의 연산을 하여야 한다는 것이 문제의 조건이다.

곱셈을 하면 숫자가 급격히 커지므로, 일정 수 이상이 되면 (혹은 아예 처음부터) 곱셈을 한 결과는 항상 덧셈을 한 결과보다 크게 된다.

즉, 곱셈을 먼저 할 수 있는 만큼 하고(그나마 처음에 숫자가 작을 때)

곱셈을 한 결과가 덧셈을 한 결과보다 커지면 그때부터는 덧셈만 해준다.

 

이 문제에서 숫자는 매우 크다. 10의 18승. 즉, 일일이 처음부터 하나씩 계속 곱해보면서 체크하면 시간 초과가 날 것이다. 이를 해결하기 위해 필자가 생각한 방법은 로그를 통해 곱셈 연산의 최대횟수를 미리 찾아두는 것이다.

문제의 조건에서 A는 2부터 시작한다는 점에 착안한 것이다. 필자의 이분탐색 관련 포스팅에서 자연수 중에서 2가 로그의 밑으로 오는 수중에서 가장 작지만, 이미 그것만으로도 엄청난 효과를 낸다는 점을 언급하였다.

X가 초기값이고 Y가 상한 인데, Y/X는 곱셈을 할 수 있는 부분이 된다. 이때, A가 2라고 가정을 해버리는 것이다.

from math import log
v = int(log(y//x, 2))

위와 같이 (파이썬) 로그 함수를 통해 밑을 2로 두고 v를 구하였다. v는 곱셈을 할 수 있는 최대 횟수를 의미하게 된다. 10^18이라는 엄청나게 큰 수이지만 로그 2를 취함으로써 단 몇십 번의 연산만 해보면 되도록 하였다.

이제 아래와 같이, v부터 시작하여 하나씩 낮춰가면서 해당 횟수만큼 곱셈을 한 것이 덧셈을 한 것보다 큰지 확인한다. 만약 크다면, 당연히 곱셈횟수를 줄여야 하는 것이고, 덧셈한 것보다 작아지거나 같아지면 그때부터는 덧셈만 하면 되므로 루프를 종료한다.

for i in range(v, 0, -1):
    mid = x*power(a, i)
    if mid <= (x*power(a, i-1)+b):
        v = i
        flag = True
        break

그리고 남은 수에서 덧셈을 몇번 할 수 있는지 구해서 합해주면 총 연산 횟수를 구할 수 있다.

 

<코드>

X는 Y보다 작아야한다. Y로 딱 떨어지는 케이스에 유의하자

수가 너무 커서 C++이 아닌 파이썬을 활용하였다.

from math import log
import sys
si = sys.stdin.readline


def power(base, exp):
    if not exp:
        return 1
    if exp % 2:
        return base*power(base, exp-1)
    temp = power(base, exp//2)
    return temp*temp


flag = False
x, y, a, b = [int(e) for e in si().split()]
v = int(log(y//x, 2))
for i in range(v, 0, -1):
    mid = x*power(a, i)
    if mid <= (x*power(a, i-1)+b):
        v = i
        flag = True
        break

if flag:
    q = (y-mid)//b
    if (y-mid) % b:
        print(q+v)
    else:
        print(q+v-1)
else:
    q = (y-x)//b
    if (y-x) % b:
        print(q)
    else:
        print(q-1)