[코드트리] 토끼와 경주

문제 링크

토끼와 경주

구현 방식

• 구현은 괜찮았는데 시간 제한이 너무 빡셌다.. d가 10억이어서 토끼들이 이동하는 과정에서 for문을 돌면 안되고 공식을 이용해서 처리해줘야한다
  • 예를 들어 x축 방향에서 '상'방향으로 움직일 때, 아래 처럼 공식을 이용해서 처리해줄 수 있다

nx = (x+d)%(2*(N-1))
if nx >= N: nx = 2*(N-1) - nx

• rabbit은 "pid: [한번에 이동하는 거리, 현재까지의 점수]" 형식의 dictionary로 선언해주었다
• prior_global은 라운드 당 움직일 토끼를 선택하는 용도의 heap이다. [[총 점프 횟수, 행번호+열번호, 행번호, 열번호, pid] ... ] 형식이다.
• 라운드 당 움직일 토끼를 선택할 때 -> 최소힙 이용
• K번의 턴이 진행된 후 점수 S를 부여받을 토끼를 선택할 때 -> 최대힙 이용
• 상하좌우 중 어느 방향으로 이동할 지 선택할 때 -> 최대힙 이용

코드

import sys
import heapq

dx = (0, -1, 0, 1)
dy = (-1, 0, 1, 0)

Q = int(sys.stdin.readline().strip())
N, M = -1, -1
rabbit = dict() #pid: [d, score]
prior_global = [] #움직이는 토끼 선택용 [[총 점프 횟수, 행번호+열번호, 행번호, 열번호, pid] ... ]

def start_200(K, S):
    prior_local = [] #마지막 점수주는 토끼 선택용
    for k in range(K):
        tjcnt, _, x, y, pid = heapq.heappop(prior_global)
        d = rabbit[pid][0]
        tmp = []

        # d가 1,000,000,000
        nx, ny = x, y

        #상
        nx = (x+d)%(2*(N-1))
        if nx >= N: nx = 2*(N-1) - nx
        heapq.heappush(tmp, [-(nx+y), -nx, -y]) #최대힙

        #하
        nx = (x-d)%(2*(N-1))
        if nx >= N: nx = 2*(N-1) - nx
        heapq.heappush(tmp, [-(nx+y), -nx, -y]) #최대힙

        #좌
        ny = (y+d)%(2*(M-1))
        if ny >= M: ny = 2*(M-1) - ny
        heapq.heappush(tmp, [-(x+ny), -x, -ny]) #최대힙

        #우
        ny = (y-d)%(2*(M-1))
        if ny >= M: ny = 2*(M-1) - ny
        heapq.heappush(tmp, [-(x+ny), -x, -ny]) #최대힙

        _, nx, ny = tmp[0]; nx, ny = -nx, -ny
        for key, value in rabbit.items():
            if key != pid:
                rabbit[key][1] += nx+ny+2

        heapq.heappush(prior_global, [tjcnt+1, nx+ny, nx, ny, pid])
        heapq.heappush(prior_local, [-(nx+ny), -nx, -ny, -pid]) #최대힙임

    _, x, y, pid = heapq.heappop(prior_local); x, y, pid = -x, -y, -pid
    rabbit[pid][1] += S

def chageDist_300(pid, L):
    rabbit[pid][0] *= L

def best_400():
    max_s = -1
    for key, value in rabbit.items():
        s = value[1]
        max_s = max(max_s, s)
    print(max_s)
        

for q in range(Q):
    cmd = list(sys.stdin.readline().strip().split())
    if cmd[0] == "100": #경주 시작 준비
        N = int(cmd[1]); M = int(cmd[2]); P = int(cmd[3]); cmd = cmd[4:]
        for i in range(0, len(cmd), 2):
            pid, d = int(cmd[i]), int(cmd[i+1])
            rabbit[pid] = [d, 0]
            heapq.heappush(prior_global, [0, 0, 0, 0, pid])
        
    elif cmd[0] == "200": #경주 진행
        K = int(cmd[1]); S = int(cmd[2])
        start_200(K, S)
    elif cmd[0] == "300": #이동거리 변경
        pid = int(cmd[1]); L = int(cmd[2])
        chageDist_300(pid, L)
    elif cmd[0] == "400": #최고의 토끼 선정
        best_400()