[Algorithm] 땅따먹기

[hwangJi-dev]

💬 문제

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

💬 Idea

1. 원래는 땅의 최댓값을 다니면서 다음 땅에서 전 땅의 인덱스를 밟지 않으면서 최댓값인 땅을 가도록 아이디어를 생각했었다.
2. 그러나 이렇게 되면 다음 땅일 때 최댓값을 도출할 수 있는 땅을 밟지 못할 수도 있다.
3. 따라서 DP를 사용해서 풀어야 한다는 것을 알게 되었다.

💬 풀이

func solution(land:[[Int]]) -> Int {
    var dp = land
    
    for i in 0..<land.count - 1 {
        dp[i + 1][0] += max(dp[i][1], dp[i][2], dp[i][3])
        dp[i + 1][1] += max(dp[i][0], dp[i][2], dp[i][3])
        dp[i + 1][2] += max(dp[i][0], dp[i][1], dp[i][3])
        dp[i + 1][3] += max(dp[i][0], dp[i][1], dp[i][2])
    }
    
    return dp[land.count - 1].max()!
}