[python/백준] 13371 돌핀

13371번: Dolphin

def gkatn(n):

    left, right = 1, 65536

    while left < right:

        mid = (left + right) // 2

        total = 3 * mid * (mid + 1) // 2

        if total >= n:

            right = mid

        else:

            left = mid + 1

    k = left

    yest = 3*(k-1)*k//2  

    idx = n- yest - 1

    if idx < k:

        return f"{k} dolphin" if k == 1 else f"{k} dolphins"

    elif idx < 2 * k:

        return f"{k} jump" if k == 1 else f"{k} jumps"

    else:

        return "splash"

   

def main():

    t = int(input())

    for _ in range(t):

        n = int(input())

        print(gkatn(n))

등차수열로 풀면 된다는 건 알겠는데 다해보면 시간초과 뜰 것 같았다. 열심히 고민해봤으나... 정말 모르겠어서 해석글을 찾아봤다. 근데 영어 문제라 그런가 찾아봐도 아무도 풀어두지 않았다... 자존심이 상했지만 지피티에게 털어놨다 그랬더니 지피티가 그건 이진탐색으로 찾으라그랬다. 즉, k 단계에는 3k개의 구문이 있으니(돌핀/점프/스플래시 가 각 단계의 수만큼 있음), 누적 구문은 3*k(k+1) //2 개가 있음. 예를 들어 4단계에는 3*4 = 12개의 구문이 존재하고, 4단계가 끝날때까지 총 구문 수는 3*4*5//2 = 30개 (3+6+9+12 = 30)가 있음. 나는 n이 우선 몇 단계인지 찾아야 함. 그럼 n<= 3*k(k+1) //2인 k를 찾으면 몇 단계인지 알 수 있음!

3*k(k+1) //2 <= 2 000 000 000 이면 k 가 약 65536 사이에 있고, 이제 그 사이에서 이분탐색으로 n<= 3*k(k+1) //2 이걸 조건삼아 k를 찾음. 그다음 k레벨에서 몇 번째 수인지는 직전 레벨까지의 구문 수를 n에서 빼고 +1하면 됨. 그리고 출력함