아니 이걸 왜 1시간을 풀었냐면, 문제 조건에서 로봇이 이동할 수 있을 때 한칸 이동하는 것을 못봐서...
구현은 간단했다. 윗 벨트랑 아랫 벨트를 다른 배열로 구분해서 놓고, 아랫 벨트로 들어가게 되면 무조건 로봇을 없앤다. 그리고 윗 벨트에서는 칸의 내구도랑 로봇의 유무를 따져서 그냥 시뮬레이션을 돌리면 된다.
진짜 한 칸 이동하는 걸 못봐서 개삽질을 했다..하.. 문제 제대로 읽자!!
N, K = map(int,input().split())
belt = list(map(int,input().split()))
# 0번부터 2n-1번까지 있는데,
# 0번부터 2n-2번은 한칸 앞으로 이동, 2n-1번은 0번으로 이동
# 0번 칸이 있는 위치, 올리는 위치 , n-1번 칸이 있는 위치 : 내리는 위치
uc = [0] * N # 위에 컨테이너,
dc = [0] * N # 아래 컨테이너
for i in range(len(belt)):
if i < N:
uc[i] = belt[i]
else:
dc[i-N] = belt[i]
# True : 탈 수 있음
uc_robot = [True] * N
# 회전 하는 함수
def rotate():
global uc
global dc
global uc_robot
tmp_ucr = [True]
tmp_uc = [dc[N-1]]
tmp_dc = [uc[N-1]]
for n in range(N-1):
tmp_uc.append(uc[n])
tmp_dc.append(dc[n])
tmp_ucr.append(uc_robot[n])
if not tmp_ucr[N-1]: # 내리는 위치 도달하면 내린다.
tmp_ucr[N-1] = True
uc = tmp_uc
dc = tmp_dc
uc_robot = tmp_ucr
def move(idx):
bef_idx = idx
global uc_robot
global uc
nxt = idx + 1
if uc_robot[nxt] and uc[nxt] >= 1:
# 움직일 수 있을 때 만큼 움직임
uc_robot[bef_idx] = True
uc[nxt] -= 1
uc_robot[nxt] = False
# 내리는 위치에 도달하면 내린다.
if nxt == N-1:
uc_robot[N-1] = True
def new_robot():
global uc_robot
global uc
if uc[0] >= 1:
uc_robot[0] = False
uc[0] -= 1
answer = 0
while True:
answer += 1
rotate()
# 가장 먼저 벨트에 올라간 로봇부터
for i in range(N - 2, 0, -1):
if not uc_robot[i]:
move(i)
new_robot()
count = 0
for i in range(len(uc)):
if uc[i] == 0:
count += 1
if dc[i] == 0:
count += 1
if count >= K:
break
print(answer)
크게 2가지가 있다.
첫 번째로, 문제 해석이다.
이 문제는 이 문장을 해석하는 것이 굉장히 애매했다.
격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
나는 이 말이 한줄만 연결되어 있는 것인 줄 알았는데, 그냥 무한 인덱스가 된다는 얘기인 것이다.
두 번째로, 입력을 받을 때 di로 si만큼 이동한다고 되어 있는데, 입력 조건을 보면 좌표는 최대 50 x 50 의 격자이지만, si는 1<=si<=1000 이다.
즉, 무한 인덱스라서 100정도의 칸 이동이 이뤄지는 게 아니라 1000칸을 이동하는 경우가 있다는 것.
물론 이것 또한 간단한 수식으로 처리가 가능하다.
나같은 경우는 좀 더럽지만
dy = abs(delta[d][1] * s) % N
dx = abs(delta[d][0] * s) % N
이런식으로 수학적으로 처리 해주었다.
어렵지 않은 반례지만, 굳이 적어 놓은 이유는 이걸 모르고 넘어갔으면 그냥 틀렸을 문제고, 많이 헤맸을 것이라고 생각하여, 다시 한번 문제 조건을 살펴볼 중요성을 상기 시키기 위해 짚고 넘어간다.
N,M,K = map(int,input().split())
# (r행, c열)
# [r][c]
balls = []
for _ in range(M):
balls.append(list(map(int,input().split())))
graph = [[[]for _ in range(N)] for _ in range(N)]
for r,c,m,s,d in balls:
graph[r-1][c-1].append([m,s,d])
def check(r,c):
if 0<=r<N and 0<=c<N:
return True
# 0번 부터 7번까지 방향
delta = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
def move_fireball():
global graph
global N
temp = [[[]for _ in range(N)] for _ in range(N)]
for x in range(N):
for y in range(N):
if graph[x][y]:
# 비어 있지 않으면
while graph[x][y]:
m,s,d = graph[x][y].pop()
dy = abs(delta[d][1] * s) % N
dx = abs(delta[d][0] * s) % N
if delta[d][1] < 0:
ny = y - dy
else:
ny = y + dy
if delta[d][0] < 0:
nx = x - dx
else:
nx = x + dx
if ny <= -1: # 연결되어 있으니까
ny += N
if nx <= -1:
nx += N
if ny >= N:
ny -= N
if nx >= N:
nx -= N
temp[nx][ny].append([m,s,d])
# 이동 한다.
for x in range(N):
for y in range(N):
if len(temp[x][y]) >= 2:
sm = 0
ss = 0
count = 0
prime = temp[x][y][0][2]
sd = 0 # 모두 같으면 0
while temp[x][y]:
m,s,d = temp[x][y].pop()
sm += m
ss += s
count += 1
if prime % 2 != d % 2:
sd = 1 # 그렇지 않으면 1
sm = sm // 5
ss = ss // count
if sm == 0:
continue
for i in range(4):
temp[x][y].append([sm,ss, 2*i+sd])
graph = temp
for _ in range(K):
move_fireball()
answer = 0
for x in range(N):
for y in range(N):
while graph[x][y]:
v, _, _ = graph[x][y].pop()
answer += v
print(answer)