Swift ) 프로그래머스(Lv2) - 땅따먹기 (DP)

programmers.co.kr/learn/courses/30/lessons/12913

코딩테스트 연습 - 땅따먹기

안녕하세요 후르륵짭짭 입니다.

어렵지 않은 문제인데,,, 제가 워나 DP에 약해서,,,

한 한시간 정도 걸린 것 같습니다

DP 문제이다 보니,,,, 처음에 이게 DP일까 

생각하다가,,,, 시간이 쫌 됐네요

 

** 문제 해설 **

 

 

처음에는 이 문제를 정렬로 접근 했습니다.

어차피 가장 큰 수가 정답일지 않을까해서,,,

그래서 가장 큰수를 맨 앞으로 하고 이전에 선택한 숫자랑 위치가 같으면 뒤로 넘겨주고...

하지만 이런 방식이 아니였습니다.

 

따라서 DP 방식으로 바꿔줬습니다.

func solution(_ land:[[Int]]) -> Int{
    
    var newLand : [[Int]] = []
    
    for (index ,element) in land.enumerated() {
        
        var tempLand : [Int] = Array(repeating: 0, count: 4)
        
        if index == 0 {
            newLand.append(element)
            continue
        }
        
        for plus in 0..<4{
        
        for start in 0..<4{
            
            if plus == start {
                continue
            }
            
            if newLand[index - 1][plus] + element[start] > tempLand[start] {
                tempLand[start] = newLand[index - 1][plus] + element[start]
            }
            
        }
            
            
        }
        
         newLand.append(tempLand)
        
    }
    
    let answer = newLand.last!.max()!
    
    return answer
}

다른 분들의 코드 보다 길지만,,,,,

각 행의 합을 담는 newLand를 만들어줍니다.

각 행 마다 새로운 배열을 만들어 줍니다

tempLand = [0][0][0][0] 이렇게요

그리고 이전의 합과 land의 열과 더해주면서 계산해주고

그것을 newLand에 추가해줍니다.

그리고 newLand의 마지막 행에서 최대값을 반환해주면 끝!