프로그래머스 - 땅따먹기 [Python]

 문제

 

 

 문제 상황

 

- 최소합 문제와 비슷하지만 다르다. 최소합 문제의 경우 dfs와 pruning을 이용하여 전역변수를 조정하는 방향으로 더해나갔다. 이 경우는 모든 열 번호가 겹치면 안되는 것이었다. 하지만 현재 문제는 자기 자신의 위치와 바로 위만 보면 된다. 즉, 자기 자신이 속한 줄과 그 바로 윗줄만 보면 되는 문제이므로 2줄 위의 줄은 영향을 못미친다. 

 

 해결 전략

 

- 범위가 최대 100,000 이므로 O(N^2)만 되도 100억이 된다. log100000 이 약 16.6 이므로 O(NlogN) 혹은 O(N*M) 안에 해결해야 할 것 같다.(이 경우 M이 4로 고정되있으므로 O(N)의 개념이다.)

 

- 특정 row를 기준으로 특정한 col이 있을 때 바로 윗줄에서 그 col값을 제외한 값 중 가장 큰 값을 더해 저장한다.

 

- 마지막 줄의 최대값을 출력한다.

 

 코드

 

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:])
            # max(land[i][(j+1)%4],land[i][(j+2)%4],land[i][(j+3)%4])
            # 도 가능한 표현이지만 j의 범위가 커지면 힘들어진다.
    return max(land[len(land)-1])

 

 

 해설

 

- 중요한 포인트는 어떤 한 줄의 선택이 다음 줄에는 영향을 주지만 다음 다음 줄에는 아무 영향을 줄 수없다는 것이다.

 

- 점화식이 매우 심플하였다. 

 

- 더해나가며 기존의 값을 변경하는 것에 부담을 갖지 말자.

 

 새로 학습한 것 & 실수 

 

- 문제를 보고 dp라는 것을 통찰할 수 있어야한다.

 

- dfs와 백트래킹, dp 문제를 구별할 눈을 키워야 한다.

 

 

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