반응형
https://leetcode.com/problems/grid-game
누적합을 이용한 문제였습니다.
📕 풀이방법
📔 입력 및 초기화
열 개수 colLength, 첫 번째와 두 번째 행의 누적합을 구할 prefix_row0, prefix_row1, 정답 변수 result를 선언 후 적절히 초기화합니다.
📔 풀이과정
📑 robot1의 역할:
- robot1은 게임에서 최대한 많은 점수를 가져가는 것이 목표입니다.
- 하지만 단순히 점수를 많이 가져가는 것만이 아니라, robot2가 가져갈 점수를 최소화해야 합니다.
- 따라서 robot1은 경로를 선택할 때 robot2가 가져갈 수 있는 점수의 최댓값을 최소화하는 방식으로 움직입니다.
📑 robot2의 역할:
- robot2는 robot1이 지나간 후 남은 점수 중에서 최대한 많은 점수를 가져가려고 합니다.
- robot2의 점수는 robot1이 선택한 경로에 따라 영향을 받습니다.
📑 경로 선택 기준:
- robot1은 각 열에서 두 가지 선택이 가능합니다:
- 오른쪽으로 이동 (row 0에 남은 점수): robot1이 row 0의 나머지 부분을 남겨둡니다.
- 아래로 이동하여 오른쪽으로 이동 (row 1의 누적 점수): robot1이 row 1의 일부를 남겨둡니다.
- robot2는 이 두 경우 중 더 큰 값을 선택합니다.
📑 result 갱신:
- robot1은 모든 열에 대해 가능한 경로를 시뮬레이션하고, robot2가 얻을 수 있는 점수의 최댓값을 계산합니다.
- robot1은 이 최댓값을 최소화하려고 하므로, result = min(result, max_points_second_robot)를 반복적으로 업데이트합니다.
📑 시간 복잡도
각 열마다 O(1)만에 경로 이동에 대한 점수를 계산하므로 O(n)입니다.
📑 공간 복잡도
각 grid의 한 행에 대해 두 변수를 선언했으므로 열 길이n만큼의 공간복잡도를 가집니다. 따라서 O(N)이 됩니다.
📔 정답 출력 | 반환
2번째 robot이 가질 수 있는 최대 점수를 반환합니다.
📕 Code
📔 Python3
class Solution:
def gridGame(self, grid: List[List[int]]) -> int:
colLength = len(grid[0])
prefix_row0 = [0] * colLength
prefix_row1 = [0] * colLength
prefix_row0[0] = grid[0][0]
prefix_row1[0] = grid[1][0]
for i in range(1, colLength):
prefix_row0[i] = prefix_row0[i-1] + grid[0][i]
prefix_row1[i] = prefix_row1[i-1] + grid[1][i]
total_row0_point = prefix_row0[-1]
result = float('inf')
for i in range(colLength):
points_above = total_row0_point - prefix_row0[i]
points_below = prefix_row1[i-1] if i > 0 else 0
second_robot_max_point = max(points_above, points_below)
result = min(result, second_robot_max_point)
return result*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.