처음에 python 제출은 시간초과가 나고 pypy 제출만 시간내에 통과가 됐다.
100 x 100 배열을 너무 자주 만들어서 연산이 많은 건가했는데 배열 문제는 아니었고,
상어의 이동부분을 한칸씩 다 계산해줘서 그런거였다.
제출코드
파이썬
import sys
input = sys.stdin.readline
def shark_move(r, c, s, d, z):
ds = s
while ds:
if d == 1:
k = min(ds, r)
r -= k
if r == 0:
d = turn(d)
elif d == 2:
k = min(ds, R-1-r)
r += k
if r == R-1:
d = turn(d)
elif d == 3:
k = min(ds, C-1-c)
c += k
if c == C-1:
d = turn(d)
else:
k = min(ds, c)
c -= k
if c == 0:
d = turn(d)
ds -= k
if tmp_board[r][c] == 0:
tmp_board[r][c] = (s, d, z)
else:
pre_shark = tmp_board[r][c][2]
if pre_shark < z:
tmp_board[r][c] = (s, d, z)
def turn(d):
if d % 2 == 0:
return d - 1
else:
return d + 1
delta = [(0,0), (-1, 0), (1, 0), (0, 1), (0, -1)]
R, C, M = map(int, input().split())
board = [[0] * C for _ in range(R)]
for i in range(M):
# (r, c) 위치, s 속력, d 방향, z 크기
r, c, s, d, z = map(int, input().split())
if d <= 2:
s = s % (2*R -2)
else:
s = s % (2*C -2)
board[r-1][c-1] = (s, d, z)
ans = 0
for h in range(C):
# 낚시 하기
for r in range(R):
if board[r][h] != 0:
ans += board[r][h][2]
board[r][h] = 0
break
# 상어 이동하기
tmp_board = [[0] * C for _ in range(R)]
for r in range(R):
for c in range(C):
if board[r][c] != 0:
shark_move(r, c, *board[r][c])
board = tmp_board
print(ans)자바
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static final Main mySolve = new Main();
static Shark[][] board;
static Shark[][] tmp_board;
static int R;
static int C;
static int M;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
board = new Shark[R][C];
for (int i = 0; i < M; i ++) {
st = new StringTokenizer(br.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int s = Integer.parseInt(st.nextToken());
int d = Integer.parseInt(st.nextToken());
int z = Integer.parseInt(st.nextToken());
if (d <= 2) {
s = s % (2*R -2);
} else {
s = s % (2*C -2);
}
Shark shark = new Shark(s, d, z);
board[r-1][c-1] = shark;
}
int ans = 0;
for (int h = 0; h < C; h++) {
for (int r = 0; r < R; r ++ ) {
if (board[r][h] instanceof Shark) {
ans += board[r][h].z;
board[r][h] = null;
break;
}
}
tmp_board = new Shark[R][C];
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (board[r][c] instanceof Shark) {
mySolve.sharkMove(r, c, board[r][c]);
}
}
}
board = tmp_board;
}
System.out.println(ans);
}
public void sharkMove(int r, int c, Shark shark) {
int ds = shark.s;
while (ds > 0) {
int k = 0;
if (shark.d == 1) {
k = minMethod(ds, r);
r -= k;
if (r == 0) {
shark.d = turn(shark.d);
}
} else if (shark.d == 2) {
k = minMethod(ds, R-1-r);
r += k;
if (r == R-1) {
shark.d = turn(shark.d);
}
} else if (shark.d == 3) {
k = minMethod(ds, C-1-c);
c += k;
if (c == C-1) {
shark.d = turn(shark.d);
}
} else {
k = minMethod(ds, c);
c -= k;
if (c == 0) {
shark.d = turn(shark.d);
}
}
ds -= k;
}
if (tmp_board[r][c] instanceof Shark) {
if (tmp_board[r][c].z < shark.z) {
tmp_board[r][c] = shark;
}
} else {
tmp_board[r][c] = shark;
}
}
public int minMethod(int a, int b) {
if (a > b) {
return b;
}
return a;
}
public int turn(int d) {
if (d % 2 == 0) {
return d -1;
}
return d +1;
}
}
class Shark {
int s;
int d;
int z;
public Shark(int s, int d, int z) {
this.s = s;
this.d = d;
this.z = z;
}
}접근방법
시간초과를 줄이는 방법은 상어의 이동을 하나하나 계산하지 않고 효율적으로 계산할 수 있는 방법을 찾는 것이었다.
1.상어가 이동하다가 처음 위치로 오는 경우 (방향 동일)
상어가 벽을 두 번찍고 처음 위치로 오면 맨 처음 상태와 같아진다.
즉 이 속도부분은 계산할 필요가 없는 부분이다.
이때의 이동거리는 2*R -2(세로로 움직이는 경우) 와 같고, 처음에 상어값을 받을때 처리해줬다.
if d <= 2:
s = s % (2*R -2)
else:
s = s % (2*C -2)2. 남은 속도처리
1번에서 불필요한 속도값을 줄였지만 남은 속도를 하나하나 계산하면 역시 시간초과가 난다.
남은 속도도 적절한 조치가 필요하다.
나는 남은 속도(=이동할 수 있는 거리)와 벽면까지의 거리를 계산해서 둘 중 최소값만큼 한번에 이동하는 방법을 선택했다.
이렇게 이동했을때 위치가 0 또는 R-1 이라면 벽면에 온것이므로 방향을 바꿔서 다시 계산하면된다.
ds = s
while ds:
if d == 1:
k = min(ds, r)
r -= k
if r == 0:
d = turn(d)
elif d == 2:
k = min(ds, R-1-r)
r += k
if r == R-1:
d = turn(d)
elif d == 3:
k = min(ds, C-1-c)
c += k
if c == C-1:
d = turn(d)
else:
k = min(ds, c)
c -= k
if c == 0:
d = turn(d)
ds -= k
뚝딱뚝딱