프로그래머스 Lv. 2 Swift 알고리즘 - 땅따먹기

이 문제는 꽤나 오래 걸려서 예제 답을 유추해냈는데...

막상 돌려보니 하나도 값이 안맞더라...ㅋㅋㅋㅋ 상당히 허무했던 문제였다.

왜 그럴까 하고 생각해보니 각 배열마다 중복된 max값이 존재할 경우를 고려하지 않았다는게 문제였다.

분명 고려하고자 아이패드에 써놨는데 코드 짜다보니... 잊어버렸나보다...

 

결론은 좀 어려워서 해설을 봤는데 DP(동적프로그래밍)에 관련된 문제였다.

https://school.programmers.co.kr/learn/courses/18/lessons/846

프로그래머스

프로그래머스에 정말 내용이 잘 나와있으니 참고하면 좋을듯!

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 결국 Tree처럼 하나씩 경우의 수를 따져가면서 끝까지 간다.
2. i+1번째 배열중 0번째 위치한 값은 0을 제외한 다른 위치에서 오는 값들 중 가장 큰 값과 결합하면 된다.
3. 그렇게 반복하여 land.count-1의 위치까지 내려오면 결국 land의 last 원소 중 가장 값이 큰 값이 답이된다.

 

 

* 코드

import Foundation

func solution(_ land:[[Int]]) -> Int{
    var land = land

    for i in 0..<(land.count-1) {
        land[i+1][0] += max(land[i][1], land[i][2], land[i][3])
        land[i+1][1] += max(land[i][0], land[i][2], land[i][3])
        land[i+1][2] += max(land[i][0], land[i][1], land[i][3])
        land[i+1][3] += max(land[i][0], land[i][1], land[i][2])
    }
    return land.last!.max()!
}

 

 

정리(Today I Learned)

1. 동적프로그래밍: 최적화 이론의 한 기술이며, 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

(a,b)	그냥 계산 시 연산 횟수	동적 계획법 이용시 연산 횟수
(2,2)	5	4
(4,4)	69	16
(6,8)	3002	48
(10,10)	184755	100