Skip to main content
  1. Posts/
  2. Algorithm/

BOJ 31498 장난을 잘 치는 토카 양

·292 words·2 mins
Jiho Kim
Author
Jiho Kim
달려 또 달려

📝 문제 정보
#

🧐 관찰 및 접근
#

  • 집 - 토카 - 돌돌이 형태로 있는 것 같다.
  • 매 수행마다 토카는 $B, B-K, B-2*K \cdots$ 만큼 움직이고, 돌돌이는 $D$만큼 계속 움직인다.
  • 토카가 잡힌다면, 그 순간 토카가 움직인 길이는 $D$보다 작을 것이다.
  • 따라서 토카가 어느 순간 잡혔다면, 토카와 돌돌이가 계속 움직인다고 가정하면 돌돌이는 토카보다 훨씬 왼쪽에 있게 된다.
    • 따라서 시간에 토카와 돌돌이의 위치에 단조성이 존재한다.
    • 이분 탐색을 이용할 수 있겠다.
  • 토카가 집에 도착하지도 못하는 상황, $K$가 0인상황 등 여러가지 예외 상황을 조심하자.

💻 풀이
#

  • 코드 (python):
A, B = map(int, input().split())
C, D = map(int, input().split())
K = int(input())

# 토카가 집에 도착할 수는 있는가?
# B + (B-K) + (B-2K) + ... >= A
if K > 0: # K = 0이면 무조건 도착할 수 있음
    cnt = B // K # B - cnt * K >= 0 인 최대 cnt
    tot = B * (cnt + 1) - K * (cnt * (cnt + 1)) // 2 # B + (B-K) + ... + (B - cnt * K)
    if tot < A:
        print(-1)
        exit(0)

# 토카가 집에 도착하는 타이밍이 돌돌이보다 이른가?
def toka_move(time):
    if K > 0:
        time = min(time, B // K + 1)
    return B * time - K * (time * (time - 1)) // 2

ok, ng = 10**12, 0

# 토카가 집에 도착하는 가장 빠른 타이밍
while ok - ng > 1:
    mid = (ok + ng) // 2
    if toka_move(mid) >= A:
        ok = mid
    else:
        ng = mid

if D*ok < A + C: # 아직 돌돌이가 도착하지 않았다면
    print(ok)
else:
    print(-1)
🔒

구현 코드 잠금

아래 쿠팡 링크를 방문하시면 코드가 공개됩니다.
광고 수익이 블로그 운영에 도움이 됩니다 🙏

🛒 쿠팡 방문하고 코드 보기

방문 후 잠금이 자동으로 해제됩니다