문제링크
https://www.acmicpc.net/problem/20056
코드 제출 기록 (메모리 및 시간)
제출 날짜
@4/16/2021
메모리
151888 KB
시간
2488 ms
메모
•
구현은 다소 쉬웠으나 시간초과 때문에 오래 걸린 문제
문제풀이
1. 방향원소
방향이 0~7까지 항상 고정되어 있으므로
dc = [0, 1, 1, 1, 0, -1, -1, -1]
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
Python
복사
→ 방향원소의 0, 1, 2, 3, 4, 5, 6, 7 번째 c, r 좌표의 변화를 의미
2. 전반적인 구현 아이디어
3. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동
파란색 식을 사용하여 1 번칸보다 작은 원소에 접근하면 N, N 번 칸보다 큰 원소에 접근하면 1 이 계산되도록 함
def move_marble(N):
for arr in marble:
_r = arr[0]
_c = arr[1]
_m = arr[2]
_s = arr[3]
_d = arr[4]
_r = ((_r + dr[_d] * _s) + N) % N
_c = ((_c + dc[_d] * _s) + N) % N
if _r == 0:
_r = N
if _c == 0:
_c = N
arr[0] = _r
arr[1] = _c
arr[2] = _m
arr[3] = _s
arr[4] = _d
Python
복사
Code
•
시간복잡도 무시하고 쌩구현 → 시간초과
# 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동
def move_marble(N):
for arr in marble:
_r = arr[0]
_c = arr[1]
_m = arr[2]
_s = arr[3]
_d = arr[4]
_r = ((_r + dr[_d] * _s) + N) % N
_c = ((_c + dc[_d] * _s) + N) % N
if _r == 0:
_r = N
if _c == 0:
_c = N
arr[0] = _r
arr[1] = _c
arr[2] = _m
arr[3] = _s
arr[4] = _d
if __name__ == '__main__':
marble = []
dc = [0, 1, 1, 1, 0, -1, -1, -1]
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
# N, M, K, marble 입력받기
N, M, K = map(int, input().split())
for i in range(M):
arr = list(map(int, input().split()))
marble.append(arr)
while K > 0:
K -= 1
move_marble(N)
# marble 배열 row, column 순서로 정렬
marble = sorted(marble, key=lambda x: (x[0], x[1]))
## 같은 칸에 두개 이상의 구슬이 있으면 4개로 쪼개기
for i in range(1, N+1):
for j in range(1, N+1):
# arr[0] = i, arr[1] = j 인 리스트들을 tmp에 저장
tmp = []
for arr in marble:
if (arr[0] == i) and (arr[1] == j):
tmp.append(arr)
if len(tmp) >= 2:
dd = []
sum_m = 0
sum_s = 0
for arr2 in tmp:
sum_m += arr2[2]
sum_s += arr2[3]
if arr2[4] % 2 == 0:
dd.append(0)
else:
dd.append(1)
marble.remove(arr2)
for k in range(4):
if sum_m//5 != 0:
if (dd.count(1) == len(tmp)) or (dd.count(0) == len(tmp)):
marble.append([tmp[0][0], tmp[0][1], sum_m//5, sum_s//len(tmp), 2*k])
else:
marble.append([tmp[0][0], tmp[0][1], sum_m//5, sum_s//len(tmp), 2*k + 1])
## 질량의 합 구하기
result = 0
for arr in marble:
result += arr[2]
print(result)
Python
복사
•
visited 함수를 추가하여 시간 최소화 → but...시간초과
marble = []
# 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동
def move_marble(visited, N):
for arr in marble:
_r = arr[0]
_c = arr[1]
_s = arr[3]
_d = arr[4]
visited[_r][_c].remove(arr)
_r = ((_r + dr[_d] * _s) + N) % N
_c = ((_c + dc[_d] * _s) + N) % N
if _r == 0:
_r = N
if _c == 0:
_c = N
arr[0] = _r
arr[1] = _c
arr[3] = _s
arr[4] = _d
visited[_r][_c].append(arr)
return visited
if __name__ == '__main__':
marble = []
dc = [0, 1, 1, 1, 0, -1, -1, -1]
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
# N, M, K, marble 입력받기
N, M, K = map(int, input().split())
visited = [[[] for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
arr = list(map(int, input().split()))
marble.append(arr)
visited[arr[0]][arr[1]].append(arr)
while K > 0:
K -= 1
visited = move_marble(visited, N)
# marble 배열 row, column 순서로 정렬
marble = sorted(marble, key=lambda x: (x[0], x[1]))
## 같은 칸에 두개 이상의 구슬이 있으면 4개로 쪼개기
for i in range(1, N+1):
for j in range(1, N+1):
if len(visited[i][j]) >= 2:
dd = []
sum_m = 0
sum_s = 0
num = len(visited[i][j])
for nn in range(num):
arr2 = visited[i][j][0]
sum_m += arr2[2]
sum_s += arr2[3]
if (arr2[4] % 2) == 0:
dd.append(0)
else:
dd.append(1)
marble.remove(arr2)
visited[i][j].remove(arr2)
mm = sum_m//5
ss = sum_s//num
if (dd.count(1) == num) or (dd.count(0) == num):
for k in range(4):
new_arr = [i, j, mm, ss, 2*k]
marble.append(new_arr)
visited[i][j].append(new_arr)
else:
for k in range(4):
new_arr = [i, j, mm, ss, 2*(k+1) - 1]
marble.append(new_arr)
visited[i][j].append(new_arr)
for arr in marble:
if arr[2] == 0:
marble.remove(arr)
visited[arr[0]][arr[1]].remove(arr)
## 질량의 합 구하기
result = 0
for arr in marble:
result += arr[2]
print(result)
Python
복사
•
성공(?)한 코드!
•
질량이 0인 구슬은 아예 추가를 하지 않도록 수정 (빨간색 부분)
marble = []
# 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동
def move_marble(visited, N):
for arr in marble:
_r = arr[0]
_c = arr[1]
_s = arr[3]
_d = arr[4]
visited[_r][_c].remove(arr)
_r = ((_r + dr[_d] * _s) + N) % N
_c = ((_c + dc[_d] * _s) + N) % N
if _r == 0:
_r = N
if _c == 0:
_c = N
arr[0] = _r
arr[1] = _c
arr[3] = _s
arr[4] = _d
visited[_r][_c].append(arr)
return visited
if __name__ == '__main__':
marble = []
dc = [0, 1, 1, 1, 0, -1, -1, -1]
dr = [-1, -1, 0, 1, 1, 1, 0, -1]
# N, M, K, marble 입력받기
N, M, K = map(int, input().split())
visited = [[[] for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
arr = list(map(int, input().split()))
marble.append(arr)
visited[arr[0]][arr[1]].append(arr)
while K > 0:
K -= 1
visited = move_marble(visited, N)
# marble 배열 row, column 순서로 정렬
marble = sorted(marble, key=lambda x: (x[0], x[1]))
## 같은 칸에 두개 이상의 구슬이 있으면 4개로 쪼개기
for i in range(1, N+1):
for j in range(1, N+1):
if len(visited[i][j]) >= 2:
dd = []
sum_m = 0
sum_s = 0
num = len(visited[i][j])
for nn in range(num):
arr2 = visited[i][j][0]
sum_m += arr2[2]
sum_s += arr2[3]
if (arr2[4] % 2) == 0:
dd.append(0)
else:
dd.append(1)
marble.remove(arr2)
visited[i][j].remove(arr2)
mm = sum_m//5
ss = sum_s//num
if mm != 0:
if (dd.count(1) == num) or (dd.count(0) == num):
for k in range(4):
new_arr = [i, j, mm, ss, 2*k]
marble.append(new_arr)
visited[i][j].append(new_arr)
else:
for k in range(4):
new_arr = [i, j, mm, ss, 2*(k+1) - 1]
marble.append(new_arr)
visited[i][j].append(new_arr)
# for arr in marble:
# if arr[2] == 0:
# marble.remove(arr)
# visited[arr[0]][arr[1]].remove(arr)
## 질량의 합 구하기
result = 0
for arr in marble:
result += arr[2]
print(result)
Python
복사
