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

프로그래머스

---

나의 풀이

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

풀이 키워드

DP
주어진 2차원 배열 land를 새로운 변수 myland에 넣어 초기화합니다.
myland는 앞으로 최대값을 저장할 배열이 됩니다.

for문은 1부터 land의 최대 행까지 반복합니다.

for문의 i가 1일 때
myland[1][0] 에 myland[0][1],myland[0][2],myland[0][3] 중 제일 큰 값을 더해줍니다.
myland[1][1] 에는 myland[0][0],myland[0][2],myland[0][3] 중 제일 큰 값을 더해줍니다.
즉, 1행에 있는 4개의 열에 그 전 행인 myland[0]의 본인 인덱스를 제외한 값 중 최대값을 더해준 겁니다.
해당 코드는 1행부터 최대의 값을 4열 중 하나에 저장해 가며
반복이 진행되며 최선의 최대값을 저장해가며 저장됩니다.
마지막 행에는 4가지 루트로 최대값을 더한 값이 있을 거고
그중 최대값을 뽑으면, 해당 값이 최고점이 됩니다.

예시)

입력 값
land = [[4, 3, 2, 1], [2, 2, 2, 1], [6, 6, 6, 4], [8, 7, 6, 5]]

myland변수의 값 변화 과정
[[4, 3, 2, 1], [5, 6, 6, 5], [6, 6, 6, 4], [8, 7, 6, 5]]
[[4, 3, 2, 1], [5, 6, 6, 5], [12, 12, 12, 10], [8, 7, 6, 5]]
[[4, 3, 2, 1], [5, 6, 6, 5], [12, 12, 12, 10], [20, 19, 18, 17]]

---