[Swift Algorithm] RGB거리 BOJ #1149

문제 설명

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

 

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

입출력 예제

입력

3
26 40 83
49 60 57
13 89 99

출력

96

 

내 문제 풀이

let n = Int(readLine()!)!
var red = Array(repeating: 0, count: n)
var green = Array(repeating: 0, count: n)
var blue = Array(repeating: 0, count: n)

for i in 0..<n {
    let now = readLine()!.split(separator: " ").map({Int(String($0))!})
    
    if i == 0 {
        red[0] = now[0]
        green[0] = now[1]
        blue[0] = now[2]
    }
    else {
        red[i] = min(green[i-1], blue[i-1]) + now[0]
        green[i] = min(red[i-1], blue[i-1]) + now[1]
        blue[i] = min(red[i-1], green[i-1]) + now[2]
    }
}

print(min(red.last!, green.last!, blue.last!))

👉 DP 문제로, 집 마다 어떤 색을 칠했다는 전제를 바탕으로 세 가지 경우의 수를 만들어주는게 포인트!

이 문제는 이전에 풀었던 #2579 계단오르기 문제와 흡사하므로, 참고!

 

[풀이 설명]

• 1, 2, 3 색이 있다고 하고, 각각 1을 골랐을 때, 2, 그리고 3을 골랐다고 가정하는 경우의 수를
  메모이제이션으로 기록하여 마지막에 그 중 최솟값을 출력해주어야한다.
• 대표로 1, 빨간색을 골랐다고 하는 경우의 수를 따져보자.
  어떤 집을 빨간색으로 칠한다는 것은 바로 이전 집은 초록이나 파랑을 골랐다는 것을 의미한다.
  따라서 1을 고르는 경우의 수를 기록하는 red 배열에,
  green 배열과 blue 배열의 이전 위치 중 더 작은 수를 골라서 더하여 저장해주면 된다.
• 빨간색뿐만 아니라 초록, 파랑의 경우에도 마찬가지로 위의 시행과 같이 반복하면 된다.
• 그리고 그 외로, 첫 번째 집은 이전 집과 비교할 수 없으므로, 특별한 연산 없이
  바로 red, green, blue 배열에 모두 해당 색깔 값을 저장해주면 된다.

[코드 설명]

• 각각 red, blue, 그리고 green을 골랐다고 하는 경우의 수를 담을 배열을 생성했다.
• for 반복으로 집 마다의 색깔 가격을 받아오면서 바로바로 연산을 진행했다.
• i가 0일 경우, 첫 번째 집을 의미하므로 이 때는 각 배열에 해당 가격을 그대로 넣어주었다.
• 그 외의 경우에는 각 색깔별로 위에서 설명한 풀이와같은 연산을 실행했다.

 

💡 피드백

• 바로 전에 풀었던 문제와 정말 유사해서 금방 풀 수 있었고,
  이러한 유형의 문제가 있다는 것을 공부할 수 있었다.
  비슷한 문제들을 더 많이 풀어보면 익숙해질 수 있을 것 같다.

 

---

문제

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