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하면 됨. 그리고 출력함
'Koala - 19기 > 코딩테스트 심화 스터디' 카테고리의 다른 글
[백준/Python] #23827 수열(Easy) (0) | 2025.07.20 |
---|---|
[python] 백준 19951 (0) | 2025.07.16 |
[백준/Python] #15686: 치킨 배달 (0) | 2025.07.13 |
[백준/python] 1051번 : 숫자 정사각형 (0) | 2025.07.13 |
[백준/Python]#14620 꽃길 (0) | 2025.07.13 |