[코드트리/삼성SW역량테스트] 토끼와 경주 (Python)

Problem : https://www.codetree.ai/training-field/frequent-problems/problems/rabit-and-race

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 01:09:23

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

1. 토끼의 경주 도중 score 관리에 주의하자. score 도중 경주를 업데이트하게 되면, 한 턴에 P-1번의 스코어 갱신이 필요해진다. 또한 최대 경주 큐 Q'가 2000 이하이므로, 최악의 경우 2000 * K * (P-1)의 업데이트가 필요하다. 따라서 P-1번 스코어를 더해주기보다는, 나머지 1마리 토끼의 스코어를 빼는 게 빠르다. 경주 도중 score는 저장해 두었다가 마지막에 합산하면 된다.

 

2. 우선순위 큐 사용 시 priority를 잘 구현하도록 하자.

 

3. 현재 라운드에서의 움직임 / 전체 라운드에서의 움직임이 구분되어야 한다. 현재 라운드에서의 움직임은 나중에 우승자를 가릴 때 쓰이며, 전체 라운드에서의 움직임은 우선순위 선정에 사용된다.

 

풀이 코드

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]

Q = int(input())
N, M, P = 0, 0, 0
race_score = 0
rabbit_dict = dict()
rabbit_q = list()

class Rabbit :
    def __init__(self, pid, d) :
        self.pid = pid
        self.d = d
        self.r = 0
        self.c = 0
        self.cur_moved = 0
        self.moved = 0
        self.score = 0

    def move(self) :
        br, bc = -1, -1
        for i in range(4) :
            MOD = 2*M-2 if i % 2 else 2*N-2
            r, c = self.r, self.c
            if i % 2 == 0 :
                r = (r + dr[i]*self.d) % MOD
                if r >= N :
                    r = MOD - r
            else :
                c = (c + dc[i]*self.d) % MOD
                if c >= M :
                    c = MOD - c
            if (br + bc, br, bc) < (r + c, r, c) :
                br, bc = r, c
        
        self.r = br
        self.c = bc
        self.moved += 1
        self.cur_moved += 1
        return br + bc + 2

    def change(self, L) :
        self.d *= L

    def priority(self) :
        return (self.r + self.c, self.r, self.c, self.pid)

def init() :
    global N, M, P
    _, N, M, P, *rabbit_info = map(int, input().split())
    for i in range(0, len(rabbit_info), 2) :
        pid, d = rabbit_info[i:i+2]
        rabbit_dict[pid] = Rabbit(pid, d)
        heappush(rabbit_q, (0, 0, 0, 0, pid))

def race_progress(K, S) :
    global race_score
    for pid in rabbit_dict.keys() :
        rabbit_dict[pid].cur_moved = 0

    for _ in range(K) :
        _, _, _, _, pid = heappop(rabbit_q)
        score = rabbit_dict[pid].move()
        priority = (
            rabbit_dict[pid].moved,
            rabbit_dict[pid].r + rabbit_dict[pid].c,
            rabbit_dict[pid].r,
            rabbit_dict[pid].c,
            pid)
        race_score += score
        rabbit_dict[pid].score -= score
        heappush(rabbit_q, priority)
    
    best_pid = -1
    best_priority = (-1, -1, -1, -1)
    for pid in rabbit_dict.keys() :
        if rabbit_dict[pid].cur_moved and best_priority < rabbit_dict[pid].priority() :
            best_pid, best_priority = pid, rabbit_dict[pid].priority()
    rabbit_dict[best_pid].score += S

def change_move_dist(pid, L) :
    rabbit_dict[pid].change(L)

def find_best_rabbit() :
    best_score = -1
    for pid in rabbit_dict.keys() :
        best_score = max(best_score, rabbit_dict[pid].score + race_score)
    print(best_score)

init()
for _ in range(Q-1) :
    q, *query = map(int, input().split())
    if q == 200 :
        K, S = query
        race_progress(K, S)
    elif q == 300 :
        pid, L = query
        change_move_dist(pid, L)
    else :
        find_best_rabbit()

풀이 완료!