문제

문제 링크

코드

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])

깨달은 점

• 그리디 막히면 무조건 모든 경우를 다룰 수 있는 방법을 생각해야 됨
  
• 그리디는 크게 큰 거 순으로 정렬, 작은 순으로 정렬이 있으니 두 기준이 안 먹히면 꼭 모든 경우를 다 순회하는 방법을 사용하자
  
• 모든 경우를 순회할 때 시간 복잡도가 매우 커진다면, 한번 처리할 때마다 이전 값을 기억하도록 해서 한번의 순회만으로 답을 구할 수 있는 동적 계획법을 사용하는게 좋다.좋은 예시가 누적합이다.

누적합 유형

1. 최소 비용의 경로
   a. 2차원 배열에서의 최소 비용 경로도 누적합으로 구할 수 있다.
   b. 이때 방향에 제한이 있어도 상관 없다.
   c. 즉, 계단이든 지도이든 상관 없다는 뜻이다.