문제
접근
DP 문제이다.
n * 4의 배열을 만들어두고, 현재 열의 최대값을 4개 모두 구해준다.
각 자리의 최대값은 현재 값 + 이전 열에서 현재 위치를 제외한 3개 중 최대값이다.
i는 현재 열을 나타내며 j는 4칸중하나 즉, 0~3의 범위이다.
최종 답은
dp[n-1] 중 최대값이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def solution(land):
dp = land[:]
for i in range(1, len(land)):
for j in range(len(land[i])):
maxNum = findMax(j, dp[i-1])
dp[i][j] += maxNum
answer = max(dp[len(land)-1])
return answer
def findMax(idx, l):
maxNum = 0
for i in range(len(l)):
if idx == i:
continue
if maxNum < l[i]:
maxNum = l[i]
return maxNum