[Python] 20056. 마법사 상어와 파이어볼

www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

---

 

Point

• 첫 입력에서 서로 다른 두 파이어볼 위치가 같은 경우는 없음
• 파이어볼 질량이 0 이 되면 소멸

 

 

 

Tip

• 2차원 리스트 배열을 선언하여 이동이 끝난 뒤 파이어볼 합치기/분열을 연산
• 파이어볼의 방향을 연산할 때, 총합이 짝수/홀수냐로 모두 짝수/홀수인지 아닌지를 판별하면 안된다.
  짝짝홀홀일 때 총합은 짝수이기 때문이다. 

 

메모리 (제한: 512MB)

138280 KB

시간 (제한: 1초)

488 ms

결과

100%

 

import sys
input = sys.stdin.readline

n,m,k = map(int, input().split())
fireballs = []
for _ in range(m):
​​​​_r,_c,_m,_s,_d = map(int, input().split())
​​​​fireballs.append([_r-1,_c-1,_m,_s,_d])
dydx = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]

for _ in range(k):
​​​​MAP = [[[] for _ in range(n)] for _ in range(n)]

​​​​# 모든 파이어볼 이동
​​​​while fireballs:
​​​​​​​​cy,cx,cm,cs,cd = fireballs.pop(0)
​​​​​​​​ny = (cy + cs*dydx[cd][0])%n
​​​​​​​​nx = (cx + cs*dydx[cd][1])%n
​​​​​​​​MAP[ny][nx].append([cm,cs,cd])

​​​​# 이동이 끝난 뒤 2개 이상칸에서는 합치고 분열
​​​​tmp = []
​​​​for r in range(n):
​​​​​​​​for c in range(n):
​​​​​​​​​​​​if MAP[r][c]:
​​​​​​​​​​​​​​​​if len(MAP[r][c]) == 1:
​​​​​​​​​​​​​​​​​​​​tmp.append([r,c]+MAP[r][c][0])
​​​​​​​​​​​​​​​​​​​​# answer += MAP[r][c][0][0]
​​​​​​​​​​​​​​​​else:
​​​​​​​​​​​​​​​​​​​​cnt = len(MAP[r][c])
​​​​​​​​​​​​​​​​​​​​sum_m = 0
​​​​​​​​​​​​​​​​​​​​sum_s = 0
​​​​​​​​​​​​​​​​​​​​cnt_odd = 0
​​​​​​​​​​​​​​​​​​​​cnt_even = 0
​​​​​​​​​​​​​​​​​​​​while MAP[r][c]:
​​​​​​​​​​​​​​​​​​​​​​​​_m,_s,_d = MAP[r][c].pop(0)
​​​​​​​​​​​​​​​​​​​​​​​​sum_m += _m
​​​​​​​​​​​​​​​​​​​​​​​​sum_s += _s
​​​​​​​​​​​​​​​​​​​​​​​​if _d % 2 == 1:
​​​​​​​​​​​​​​​​​​​​​​​​​​​​cnt_odd += 1
​​​​​​​​​​​​​​​​​​​​​​​​else:
​​​​​​​​​​​​​​​​​​​​​​​​​​​​cnt_even += 1

​​​​​​​​​​​​​​​​​​​​# 짝 짝 홀 홀 이어도 합이 양수가 나올 수 있음
​​​​​​​​​​​​​​​​​​​​# 방향이 모두 양수/음수인지 판별
​​​​​​​​​​​​​​​​​​​​flag = False
​​​​​​​​​​​​​​​​​​​​if cnt_odd == cnt or cnt_even == cnt:
​​​​​​​​​​​​​​​​​​​​​​​​flag = True

​​​​​​​​​​​​​​​​​​​​if sum_m//5 > 0:
​​​​​​​​​​​​​​​​​​​​​​​​if flag:
​​​​​​​​​​​​​​​​​​​​​​​​​​​​for nd in [0,2,4,6]:
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​tmp.append([r,c,sum_m//5,sum_s//cnt,nd])
​​​​​​​​​​​​​​​​​​​​​​​​elif not flag:
​​​​​​​​​​​​​​​​​​​​​​​​​​​​for nd in [1,3,5,7]:
​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​​tmp.append([r,c,sum_m//5,sum_s//cnt,nd])
​​​​​​​​​​​​​​​​​​​​​​​​# answer += (sum_m//5)*4
​​​​​​​​​​​​​​​​​​​​# 질량이 0 인 파이어볼은 소멸
​​​​​​​​​​​​​​​​​​​​else:
​​​​​​​​​​​​​​​​​​​​​​​​continue
​​​​fireballs = tmp

answer = sum([f[2] for f in fireballs])
print(answer)

 

문제를 푸는데 도움이 된 테스트 케이스