https://www.acmicpc.net/problem/17143
문제를 이해하면서 문제를 크게 3가지 작은 문제로 쪼갰다.
1. 특정열에 존재하는 상어들 중 제일 위쪽에 있는 상어 제거하기
2. 상어 각각 이동시키기
3. 같은칸에 있는 상어면 큰 것만 남기기
이때 2.파트가 핵심이라고 느꼈고, 어떻게 구현할지 고민하면서 시간복잡도를 따져보니 상어를 각각 이동시킬때 한칸씩 이동하도록 코드를 짜면 총 10억으로 시간 초과가 날 것으로 보였다.
그래서 시간복잡도를 줄이기 위한 방법을 찾았고, 좌우를 똑같이 왕복하면 같은 상태가 되는 점을 이용해 나머지 연산을 통해 시간복잡도를 줄였다. 이때, 구체적인 예시를 적어서 방법을 찾았던게 좋은 방법이었던 것 같다.
1,3 파트의 경우 모두 정렬을 이용해서 풀었는데, 더 나은 풀이가 없을지 찾아봐야겠다.
추가로 관련된 정보를 Class로 모아서 관리하는게 코드를 짤 때 훨씬 직관적이어서 개인적으로 잘 맞는 것 같다. 그리고, 1,2,3,4와 같은 값을 코드 상단에서 UP, DOWN, LEFT, RIGHT로 정의해두고 코드에서 쓰는 것도 유용했다.
인덱스가 1부터 시작하는게 문제에서 주어지면 이 부분을 계속 고려하면서 코드를 작성하자. 한번 헷갈리면 다 꼬인다.
[시간 초과 관련]
Python3로 제출했을때 시간초과가 나서 sys.stdin.readline을 추가했고, 그래도 시간초과가 나서 PyPy3로 제출하니 통과되었다.
import sys
input = sys.stdin.readline
UP, DOWN, RIGHT, LEFT = 1, 2, 3, 4
DX_DY = [None, (-1, 0), (1, 0), (0, 1), (0, -1)]
def change_direction(dir): # 방향 전환
if dir == UP:
return DOWN
elif dir == DOWN:
return UP
elif dir == LEFT:
return RIGHT
elif dir == RIGHT:
return LEFT
else:
print("error")
def is_valid(x, y): # 격자 범위 안에 있는지
if 0 <= x < R and 0 <= y < C:
return True
return False
class Shark:
def __init__(self, r, c, s, d, z):
self.x = r # 인덱스 0부터
self.y = c # 인덱스 0부터
self.speed = s
self.direction = d # 1(UP),2(DOWN),3(RIGHT),4(LEFT)
self.size = z
def move(self): # 1초 후
if self.direction in [LEFT, RIGHT]:
self.speed %= ((C - 1) * 2)
else: # UP,DOWN
self.speed %= ((R - 1) * 2)
for _ in range(self.speed): # 이만큼 이동 위에서 나머지해서 max 99
dx, dy = DX_DY[self.direction]
if is_valid(self.x + dx, self.y + dy):
self.x, self.y = self.x + dx, self.y + dy
else:
# Direction 바꾸고 이동
self.direction = change_direction(self.direction)
dx, dy = DX_DY[self.direction]
self.x, self.y = self.x + dx, self.y + dy
R, C, M = map(int, input().split())
sharks = []
for _ in range(M):
r, c, s, d, z = map(int, input().split())
r, c = r - 1, c - 1 # 인덱스 0기준으로
sharks.append(Shark(r, c, s, d, z))
ans = 0
for remove_y_idx in range(C): # 0~C-1
# 1. 해당 열 중 가장 위에 있는 상어 제거
sharks.sort(key=lambda shark: (shark.x)) # 처음발견된게 행이 가장 작도록
for i, shark in enumerate(sharks):
if shark.y == remove_y_idx:
ans += shark.size
sharks.pop(i)
break
# 2. 상어 이동
for shark in sharks:
shark.move()
# 3. 같은 위치에 상어 여러개면 큰 것만 남기기
new_sharks = []
check_x_y = set()
sharks.sort(key=lambda shark: -shark.size) # 크기 큰게 무조건 먼저
for shark in sharks:
if (shark.x, shark.y) in check_x_y:
continue # 이미 있으면
new_sharks.append(shark)
check_x_y.add((shark.x, shark.y))
sharks = new_sharks
print(ans)