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

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

프로그래머스

DP

| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |

 

이런 4열 N행의 숫자가 쓰여있는 판이 있을 때

가로 한줄마다 한칸씩 밟아가면서 차례대로 내려갈 수 있다고 한다.

단 같은 열의 아래층으로 내려갈 순 없음.

 

이때, 마지막 줄까지 내려가는데 얻을 수 있는 최고점 출력하기

 

접근방법

DFS도 아니고 오직 DP인 문제였다

land와 똑같은 형태인 dp배열에, (r,c)칸에는 (r,c)까지 오는데 얻을 수 있는 최고점이 저장되어야 한다. - 이게 부분 문제

그리고

맨 윗줄부터 한칸씩 N-1행까지 반복문을 돌면서

현재 위치한 칸에서 갈 수 있는 바로 다음줄의 칸들의 dp값을 갱신해준다.

즉,,(r,c)칸이면 -> (r+1, nc = 0~3 (!= c)) 이 범위의 칸들의 dp 값을 모두 갱신한다.

어떻게 갱신? -> 새로 밟을 칸의 원래 dp값(기존 최고점수) vs. (r,c)칸까지의 최고점수(dp[r][c]) + 새로 밟을 칸(r+1, nc)의 점수 (land[r+1][nc]) = (r,c)칸 밟고 새로 밟은 칸 밟았을 때의 점수

 

[예외처리 구간]

그리고 1개의 행일때는 반복문을 돌 수 없기 때문에(다음칸으로 내려갈 수 없음) 그냥 그 한줄의 최댓값을 출력한다.

 

소스코드

import Foundation

func solution(_ land:[[Int]]) -> Int{    
    var dp:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: 4), count: land.count)
    
    dp[0] = land[0]
    
    if land.count == 1 {
        return dp[0].max() ?? 0 
    }
    
    for r in 0..<land.count-1 {
        for c in 0..<4 {
            //내려가기
            for i in 0..<4 {
                if c == i { continue }
                dp[r+1][i] = max(dp[r+1][i], dp[r][c]+land[r+1][i])
            }
        }
    }
    
    return dp[land.count-1].max() ?? 0
}

 

 

아니 프로그래머스 가끔 똑같은 코드인데 결과 다르게 나올 때 있음..

ex. 띄어쓰기 했다가 안했더니 시간초과 났던게 안난다던가..