백준 1149 RGB 거리

출처: https://www.acmicpc.net/problem/1149

분류: DP

---

접근방식

dp 문제임은 알았지만 결국 풀지 못하고 다른 분들의 풀이를 참고했습니다 ㅠㅠ

처음에는 r, g, b에서 시작한 dp 3개를 다 채우면 되지않을까 생각을 했는데 이렇게 하면 두 색의 비용이 같거나 하는 등의 여러 예외들을 처리해줄 수가 없게됩니다 ㅠㅠ

기존에서 사고를 좀 더 열어 생각해보면 각 집이 모두 r, g, b로 칠해질 수 있는 경우를 생각해보면 쉽게 접근할 수 있습니다 :)

일반적인 1차원 배열이 아니라 [집의 개수][3] 크기의 2차원 배열을 채워나가는 방식으로 접근하면 쉽게 해결할 수 있었습니다.

 

해결방법

let numberOfHouse = Int(readLine()!)!
var colorSet = [[Int]]()
for _ in 0..<numberOfHouse {
    colorSet.append(readLine()!.split(separator: " ").map({ Int(String($0))! }))
}

var dp = [[Int]](repeating: [Int](repeating: 0, count: 3), count: numberOfHouse)

dp[0][0] = colorSet[0][0]
dp[0][1] = colorSet[0][1]
dp[0][2] = colorSet[0][2]

for idx in 1..<numberOfHouse {
    for color in 0..<3 {
        let other1 = (color+1) % 3
        let other2 = (color+2) % 3
        dp[idx][color] = min(dp[idx-1][other1] + colorSet[idx][color], dp[idx-1][other2] + colorSet[idx][color])
    }
}

print(min(dp[numberOfHouse-1][0], dp[numberOfHouse-1][1], dp[numberOfHouse-1][2]))

 

 

배운점

dp인 걸 알고도 풀지 못했다 ㅠㅠ 그래도 dp배열 자제를 2차원 배열로도 접근할 수 있다는 걸 배웠다.