import sys
input = sys.stdin.readline
INF = 10**9
def crossed(i,j):
global dead
x1,y1,x2,y2 = line[i]
x3,y3,x4,y4 = line[j]
if min(x1,x2)>max(x3,x4) or min(x3,x4)>max(x1,x2) or min(y1,y2)>max(y3,y4) or min(y3,y4)>max(y1,y2):
return INF
dead = True
if x1==x2:
return min(abs(y3-y1),abs(y4-y1))+1
else:
return min(abs(x3-x1),abs(x4-x1))+1
L = int(input())
N = int(input())
L1 = L+1
line = [(-L1,L1,L1,L1),(-L1,-L1,L1,-L1),(L1,-L1,L1,L1),(-L1,-L1,-L1,L1),(0,0,0,0)]
direction = [0]
dead = False
t = 0
for i in range(5,N+5):
l,d = input().split()
if dead:
continue
l = int(l)
if d == "L":
d = (direction[-1]-1)%4
else:
d = (direction[-1]+1)%4
direction.append(d)
x1,y1,x2,y2 = line[-1]
if direction[-2] == 0:
line.append((x2+1,y2,x2+l,y2))
elif direction[-2] == 1:
line.append((x2,y2+1,x2,y2+l))
elif direction[-2] == 2:
line.append((x2-1,y2,x2-l,y2))
else:
line.append((x2,y2-1,x2,y2-l))
x = INF
for j in range(i):
x = min(x,crossed(i,j))
if dead:
t += x
else:
t += l
if not dead:
l = 3*L
x1,y1,x2,y2 = line[-1]
if direction[-1] == 0:
line.append((x2+1,y2,x2+l,y2))
elif direction[-1] == 1:
line.append((x2,y2+1,x2,y2+l))
elif direction[-1] == 2:
line.append((x2-1,y2,x2-l,y2))
else:
line.append((x2,y2-1,x2,y2-l))
x = INF
for j in range(N+5):
x = min(x,crossed(N+5,j))
t += x
print(t)아이디어는 쉬운데 구현하는데 어려움이 꽤 있었던 문제였다.
데이터의 양이 N개이므로 O(N^2)으로 구현하였다.
일단 알고리즘을 정리하면,
1. 0,0,0,0부터 시작해서 1칸 이동한 좌표와 t칸 이동한 좌표를 양 끝점으로 하는 선분을 line 리스트에 기록한다.
2. 이전의 모든 선분에 대해 crossed인지 체크한다.
3. 만약 crossed라면 dead를 True로 바꾸고 언제 cross 되는지 값을 구하여 가장 작은 값을 저장한다.
4. cross 되는데 걸린 총 시간을 구한다.
이때 뱀이 본인의 몸 뿐만 아니라 맵 바깥으로 나가는 것도 죽는 것으로 처리해야 하는데, 일반화해서 처리하기 위해 초기 line 리스트에 맵의 바깥을 구성하는 4개의 모서리에 대한 선분을 넣어주었다.
실수하기 쉬운 포인트는
1. 입력으로 주어진 모든 t가 끝났는데도 뱀이 살아있다면, 마지막으로 바꾼 방향으로 뱀이 죽을때까지 나아가야한다.
2. 입력이 한개도 주어지지 않을 수 있다.(N이 0) 이때의 error를 주의해야 한다.
오늘의 교훈) 항상 0을 조심하자