[BOJ] 17143번: 낚시왕

https://www.acmicpc.net/problem/17143

17143번: 낚시왕

문제 해결

1. 문제는 낚시왕이 C만큼 이동하면 끝나기 때문에 1) 오른쪽으로 한 칸 이동한 후 낚시 2) 상어 이동 이걸 C만큼 반복해주면 된다.

2. 낚시를 할 땐 그 열에서 가까운 행에 상어가 있으면 잡고 나서 상어를 제거해주면 된다. (board[r][c] = 0 작업 필요)

3. 낚시가 끝났으면 이동을 해주면 되는데, 이 부분이 제일 고민이 많이 됐다. 처음엔 2중 for문으로 board에 값이 있으면 속력만큼 이동해주려고 했는데 그러면 3중 포문이 된다. 시간 초과가 걱정됐다.

속력이랑 현재 위치를 가지고 계산을 해서 한 번에 위치를 정해주는 경우를 생각해보았는데 수학식,, 머리 쓰기 싫어짐 일단 패스

일단은 3중 포문으로 해보자! 했는데 시간초과 ㅎㅎ ㅋㅋ

R, C, M = map(int, input().split())
board = [ [0] * C for _ in range(R) ]

for shark in range(M):
    r, c, s, d, z = map(int, input().split())
    board[r-1][c-1] = (s, d-1, z)

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def move():
    move_board = [ [0] * C for _ in range(R) ]
    for i in range(R):
        for j in range(C):
            if board[i][j]:
                r, c, s, d, z = i, j, board[i][j][0], board[i][j][1], board[i][j][2]

                for moving in range(s):
                    if (r == 0 and d == 0): d = 1
                    elif (c == 0 and d == 3):   d = 2
                    elif (r == (R-1) and d == 1):   d = 0
                    elif (c == (C-1) and d == 2):   d = 3

                    r += dx[d]
                    c += dy[d]

                if move_board[r][c]:
                    if move_board[r][c][2] < z:
                        move_board[r][c] = (s,d,z)
                else:
                    move_board[r][c] = (s,d,z)

    return move_board 

def solve(c):
    size = 0
    for x in range(R):
        if board[x][c] :
            size += board[x][c][2]
            board[x][c] = 0
            return size

    return size

result = 0
for i in range(C):
    result += solve(i)
    board = move()

print(result)

 

시간 초과 안 나게 하려면 상어가 이동하는 시간을 O(1)로.. 아래 코드로 이동 함수바꿔주면 통과.. 앜😇

def move_shark():
    move_board = [[0] * C for _ in range(R)]
    for i in range(R):
        for j in range(C):
            if board[x][y]:
            	r, c, s, d, z = i, j, board[i][j][0], board[i][j][1], board[i][j][2]

            total = s
            if d == 0 or d == 1:
                s %= 2 * R - 2
                while s:
                    if (r == R - 1 and d == 1) or (r == 0 and d == 0):
                        d ^= 1 
                    r += dx[d]
                    s -= 1
            else:
                s %= 2 * C - 2
                while s:
                    if (c == C - 1 and d == 2) or (c == 0 and d == 3):
                        d = (d - 2)^1 + 2
                    c += dy[d]
                    s -= 1
 
            if move_board[r][c] and move_board[r][c][2] > z:
                pass
            else:
                move_board[r][c] = (total, d, z)
                
    return move_board