[프로그래머스] 땅따먹기 (Swift)

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

프로그래머스

 

import Foundation

func solution(_ land:[[Int]]) -> Int{
    var land = land 
    let n = land.count
    
    for i in 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][1],land[i-1][0],land[i-1][3])
        land[i][3] += max(land[i-1][1],land[i-1][2],land[i-1][0])
    }
    
    return land[n-1].max()!
}

내 풀이)

* DP (Dynamic Programming)문제 - 가장 작은 부분의 해답을 구한 후 이를 저장하여 저장한 값으로 상위 문제를 풀어가는 방식

* 0번째 행의 최댓값으로 시작해서 나아가면 전체 최고점이 아닐 수 있음

* 이전에 행의 열과 현재의 행의 열이 같으면 안됨

 

1.  모든 경우의 합을 구하면 됨, 이때 이전에 행의 열과 현재의 행의 열이 같으면 안되는 것을 이용함

ex)  

  0행 1  2  3  5

  1행 5  6  7  8

1행 0열에 있는 5는 0행중에 0열(1)을 제외한 최대값(5) 을 더하여 10으로 변환해주고 

1행 1열에 있는 6는 0행중에 1열(2)을 제외한 최대값(5) 을 더하여 11로 변환해주고

1행 2열에 있는 7는 0행중에 2열(3)을 제외한 최대값(5) 을 더하여 12로 변환해주고

1행 3열에 있는 8는 0행중에 3열(5)을 제외한 최대값(3) 을 더하여 11로 변환해줌

 

2. n은 행열의 행의 갯수이므로 1에서 n-1번까지 반복

 

3. 실제 행은 0부터 시작하므로 n-1의 최댓값을 반환하면됨