문제 링크
https://www.acmicpc.net/problem/17143
문제 이해
백준에 있는 입력 예제 1이 문제를 이해하는 데에 많은 도움이 되었다.
일단 상황은 다음과 같이 진행된다.
- 낚시왕이 오른쪽으로 한 칸 이동한다.
- 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
- 상어가 이동한다.
- 주의점: 3에서 상어가 이동할 때 같은 위치에 여러 상어가 존재하게 될 경우 가장 큰 상어가 나머지 상어를 다 먹는다. (상어의 크기는 모두 다름)
접근
따라서 결론부터 말하자면 나의 알고리즘은 다음과 같은 구조로 동작한다.
ans = 0
for j in range(C):
ans += fish(j)
move()
print(ans)낚시꾼이 0에서부터 C-1까지 이동하면서 한번씩 낚는 행위를 반복하면서, 잡은 물고기의 크기만큼 답을 증가시키는 것이다.
그렇다면 이제 fish() 함수와 move() 함수를 보자.
def fish(j):
for i in range(R):
if board[i][j]:
x = board[i][j][2]
board[i][j] = 0
return x
return 0간단하다. 해당 열에 상어가 있으면 그 상어의 크기만큼을 반환해준다. 그리고 상어를 잡아갔으므로 그 자리를 0으로 설정해준다.
만일 상어가 없으면 0을 반환!
def move():
global board # board[i][j] 안에는 (s,d,z)의 값이 들어있음. 상어가 없는 경우엔 0이 들어있음
new_board = [[0 for _ in range(C)] for _ in range(R)] # 상어들의 새 위치를 담을 공간
for i in range(R):
for j in range(C):
if board[i][j]:
# 이 상어의 다음 위치는
ni, nj, nd = get_next_loc(i, j, board[i][j][0], board[i][j][1])
if new_board[ni][nj]:
new_board[ni][nj] = max(
new_board[ni][nj],
(board[i][j][0], nd, board[i][j][2]),
key=lambda x: x[2],
)
else:
new_board[ni][nj] = (board[i][j][0], nd, board[i][j][2])
board = new_board # board가 이제 상어들의 새 위치를 가리키도록다음은 move() 함수이다. 조금 복잡해보이지만, 들여다보면 쉽다. 일단은 상어들의 새 위치를 가리킬 new_board를 선언하였다.
그리고 i,j의 값을 증가시키며 board에 있는 모든 칸을 순회하면서, 상어가 있는 칸에 도달하면
- 해당 상어의 다음 위치를 계산한 후
- 다음 위치에 상어를 옮긴다. 이미 상어가 그 칸에 있으면, 큰놈으로 대체.
이제 마지막으로 다음 위치를 계산하는 함수인 get_next_loc() 에 대해 알아보겠다.
def get_next_loc(i, j, speed, dir):
if dir == UP or dir == DOWN: # i
cycle = R * 2 - 2
if dir == UP:
speed += 2 * (R - 1) - i
else:
speed += i
speed %= cycle
if speed >= R:
return (2 * R - 2 - speed, j, UP)
return (speed, j, DOWN)
else: # j
cycle = C * 2 - 2
if dir == LEFT:
speed += 2 * (C - 1) - j
else:
speed += j
speed %= cycle
if speed >= C:
return (i, 2 * C - 2 - speed, LEFT)
return (i, speed, RIGHT)일단 인자로는 i,j,speed,dir을 받는다. dir 을 이용해 이 상어가 어디로 이동할지, 행이동을 할지 열이동을 할지 알 수 있고, speed 만큼 이동시키면 된다.
그런데 상어가 0,1,2,3,4,5,0,1,2,3,4,5,... 이런식으로 움직이지 않고
0,1,2,3,4,5,4,3,2,1,0,1,2,3,4,5,4... 이런식으로 오르락 내리락 하며 움직인다.
즉, 상어가 다시 원위치로 돌아오는 것을 기준으로 cycle을 이루며 값이 변한다. cycle의 값은 항상 2*R-2이며 (또는 2*C-2)) 이는 저 수들을 보며 규칙을 찾을 수 있다.
하지만 상어도 기존의 위치가 있다. 기존의 위치만큼을 speed에 더하고 상어를 무조건 0에서 출발시키는 것이 이 함수의 목적이다.
즉, 이 함수를 요약하자면,
- 상어는 0,1,2,3,4,3,2,1,... 과 같은
cycle을 가진다- 계산을 편하고 빠르게 하기 위해 상어를 0에서 시작하는 것으로 위치를 고정하고, 기존에 있던 위치만큼을
speed에 더해준다.speed만큼 상어를 이동시킨다.
특별히 역행하는 경우(UP,LEFT) 몇가지 작업을 더 해준다.
speed에 기존의 위치만큼 더해주려면 그냥 더해주면 안되고 이 0,1,2,3,4,3,2,1 사이클에서의 위치로 더해줘야 한다.
만일 역행하는데 위치가 2에 있다면, i,j값은 그냥 2일테지만, 이 사이클 안에서는 6이 되어야 하는 것이다. 그것에 대한 작업이다.
그렇게 해서 얻은 위치가 2 * R - 2 - speed 가 되는 것이다.
정답 코드
import sys
sys.setrecursionlimit(10 ** 8)
input = lambda: sys.stdin.readline().rstrip()
def fish(j):
for i in range(R):
if board[i][j]:
x = board[i][j][2]
board[i][j] = 0
return x
return 0
def move():
global board # board[i][j] 안에는 (s,d,z)의 값이 들어있음. 상어가 없는 경우엔 0이 들어있음
new_board = [[0 for _ in range(C)] for _ in range(R)] # 상어들의 새 위치를 담을 공간
for i in range(R):
for j in range(C):
if board[i][j]:
# 이 상어의 다음 위치는
ni, nj, nd = get_next_loc(i, j, board[i][j][0], board[i][j][1])
if new_board[ni][nj]:
new_board[ni][nj] = max(
new_board[ni][nj],
(board[i][j][0], nd, board[i][j][2]),
key=lambda x: x[2],
)
else:
new_board[ni][nj] = (board[i][j][0], nd, board[i][j][2])
board = new_board # board가 이제 상어들의 새 위치를 가리키도록
def get_next_loc(i, j, speed, dir):
if dir == UP or dir == DOWN: # i
cycle = R * 2 - 2
if dir == UP:
speed += 2 * (R - 1) - i
else:
speed += i
speed %= cycle
if speed >= R:
return (2 * R - 2 - speed, j, UP)
return (speed, j, DOWN)
else: # j
cycle = C * 2 - 2
if dir == LEFT:
speed += 2 * (C - 1) - j
else:
speed += j
speed %= cycle
if speed >= C:
return (i, 2 * C - 2 - speed, LEFT)
return (i, speed, RIGHT)
UP, DOWN, RIGHT, LEFT = 1, 2, 3, 4
R, C, M = map(int, input().split())
board = [[0 for _ in range(C)] for _ in range(R)]
for i in range(M):
r, c, s, d, z = map(int, input().split())
r, c = r - 1, c - 1
board[r][c] = (s, d, z)
# s : speed
# d : 1(up), 2(down), 3(right), 4(left)
# z : size
ans = 0
for j in range(C):
ans += fish(j)
move()
print(ans)
