문제

https://programmers.co.kr/learn/courses/30/lessons/12913

나의 코드 (답안참조)

"""
1. 아이디어
문제 딱 보고 처음 든 생각이 dp문제이구나 싶었다. 
그리고 dp문제중에 예전에 풀었던 백준의 RGB거리랑 똑같다고 느꼈다. 
근데 dp문제 안 푼지가 조금 오래되서 이전에 풀었던 RGB거리 문제의 소스코드를 참조했다.

2. 시간복잡도
언뜻 보기에는 O(N^2)인거 같은데 코드 안에서 n이 행의개수(10000이하의 자연수)이고, 
반복문 내에 max()연산을 하는거는 열의 개수 즉, 4개 이니깐 4*10000 즉 40000인거 같다. 
그래서 상수 무시하고 O(N)이 맞지 않나 싶은데 계속 생각해봐야 겠다.
"""

def solution(land):
    
    n = len(land)
    
    for i in range(1, n):
        land[i][0] += max(land[i-1][1], land[i-1][2], land[i-1][3])
        land[i][1] += max(land[i-1][0], land[i-1][2], land[i-1][3])
        land[i][2] += max(land[i-1][0], land[i-1][1], land[i-1][3])
        land[i][3] += max(land[i-1][0], land[i-1][1], land[i-1][2])
        
    return max(land[n-1])
    

느낀점

시간복잡도 개념이 흔들려서 그런지 시간복잡도 계산이 굉장히 헷갈리긴 한 문제이다.
근데 처음생각대로 O(N^2)이면 문제 효율성에서 통과하지 못했을 것이다. 그래서 위에 적은 시간복잡도 계산이 맞는 것 같은데 다시 생각해봐야겠다.

DP문제 중에서는 쉬운편에 속하는 것 같다.
DP문제는 처음에 문제를 보고 DP문제인지 처음에 판단하는게 제일 중요하다.