[Swift][DP] 백준 1149번 (RGB거리)

요구능력 : DP에 대한 이해

 

코드설명 : 

 

 

26 40 83

39 60 57

13 89 99

문제를 보면 앞뒤에 나온 컬러는 사용할 수가 없다.

우선 조건없는 점화식을 만들어보자.

조건이 없다면 최소값을 누적하는 dp이다.

그렇다면 dp[i] = dp[i - 1] + arr[i][최소가되는부분] 이 만들어진다.

dp[i - 1]에는 이미 최소값이 만들어진것이라 가정한것이다.

 

조건을 넣은 점화식을 만들어보자.

우선 조건은 3가지가 있다.

R일때, G일때, B일때.

dp[i]가 R이면 이전에는 G와 B가 나와야한다.

 

아래 코드에서는 R이 0, G가 1, B가 2 이다.

 

dp[i]를 R로 칠한경우의 DP가 있을것이고, G로 칠한경우의 DP가 있을것이고, B로 칠한경우의 DP가 있을것이다.

그러므로 arr배열에 맞춰서 dp도 2차원 배열로 만들어준다.

후에 점화식을 만들면 아래와같다.

dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]

이전 dp에서 본인이 구하고자하는 부분만 가져와서 비교해서 최소값을 만든것이다.

 

내가 너무 설명을 못하는것같아서 설명 잘되어있는 링크 첨부

 

후기 : 규칙만 잘찾으면 금방풀어지는 문제

let n = Int(String(readLine()!))!
var arr: [[Int]] = [[]]
var dp: [[Int]] = Array(repeating: Array(repeating: 0, count: 4), count: n + 1)
for _ in 1...n {
    let a = readLine()!.split(separator: " ").map{Int(String($0))!}
    arr.append(a)
}

for i in 1...n {
    dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0]
    dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1]
    dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2]
}

print(min(dp[n][0], dp[n][1], dp[n][2]))