땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.
import sys
sys.setrecursionlimit(10 ** 6)
def solution(land):
row = len(land)
answer = 0
def dfs(cur_sum, cur_col, depth):
nonlocal answer
if depth == row:
answer = max(answer, cur_sum)
return
else:
# print(depth, land[depth][cur_col], cur_sum)
idxList = [i for i in range(4) if i != cur_col]
for idx in idxList:
dfs(cur_sum + land[depth][idx], idx, depth + 1)
for i in range(4):
dfs(land[0][i], i, 1)
return answer
def solution(land):
total_row = len(land)
cache = [[0] * 4 for _ in range(len(land))]
for i in range(4):
cache[0][i] = land[0][i]
#DP 시작
for ridx in range(1, total_row):
current_row = land[ridx]
for i, score in enumerate(current_row):
sliced = cache[ridx-1][:i] + cache[ridx-1][i+1:]
cache[ridx][i] = max(sliced) + score
return max(cache[-1])
def solution(land):
for i in range(1, len(land)):
for j in range(4):
land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])
이 문제는 모든 경우를 탐색해야 하지만, 시간효율적으로 탐색해야 하는 문제입니다. 또한, 이동할 수 있는 경로에 제약을 둠으로써, N+1의 위치에 왔을 때, 어디에서 N+1의 위치로 왔는지 추측할 수 있습니다.
그렇기 때문에 어떤 칸에 오는 데에 드는 비용을 기록해놓고, 다음 칸에 오는 데에 드는 비용을 위해서 활용한다면 시간효율적으로 문제를 풀 수 있습니다.
이런 느낌의 문제는 다음 문제와 같습니다.