📌문제
https://school.programmers.co.kr/learn/courses/30/lessons/12913
🎖️난이도
Level 2
✔️풀이
# sol1) DP => getMax()
def getMax(arr, idx):
now_max = 0
for i in range(4):
if i == idx:
continue
if now_max < arr[i]:
now_max = arr[i]
return now_max
def solution(land):
for i in range(1, len(land)):
for j in range(4):
land[i][j] += getMax(land[i-1], j)
return max(land[-1])
# sol2) DP => pythonic
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:])
return max(land[-1])
🧠노트
아래 행으로 점점 내려오면서 위에 과정에서 누적된 최대 값을 계속 가지고 가기 때문에
DP로 누적해가며 풀어준다.
이전 행에서의 누적 최댓값을 구할 때
getMax()를 정의해도 되고, max()안에 슬라이싱을 통해 이전 행에서 같은 열 값만 뺀 리스트를 넣어도 된다.
후자가 더 Pythonic!
🔍참고
-
'[ 알고리즘 ] > DP' 카테고리의 다른 글
[프로그래머스] N으로 표현 (2) | 2022.09.23 |
---|---|
[프로그래머스] 도둑질 (0) | 2022.06.29 |
[프로그래머스] 등굣길 (0) | 2022.06.29 |
[프로그래머스] 정수 삼각형 (0) | 2022.06.29 |
[프로그래머스] N으로 표현 (0) | 2022.06.29 |