백준 1149번 RGB거리 - SWIFT

문제

---

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보다 작거나 같은 자연수이다.

 

출력

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

 

문제 링크

1149번: RGB거리

 

 

풀이

---

문제 조건을 보면

1번 집의 색은 2번 집의 색과 같지 않아야 한다.

N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

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

이렇게 조건이 나와있는데, 한 줄 요약하자면 그냥 인접한 두 집은 색이 달라야 한다는 것이다.

 

인접한 두 집의 색이 서로 다르기만 하기 때문에 R, G, R도 가능한 패턴 중 하나다.

간단하게 경우의 수를 구해보면 맨 처음에는 3가지 경우를 택할 수 있고, 그 이후부터는 앞에서 뽑은 경우를 뽑을 수 없으므로 2가지 경우를 택할 수 있게 된다.

 

그래서 이를 단순 계산식으로 옮겨보면,

3 * 2 ^ (N - 1) 가지가 된다.

근데 우리가 받을 N은 1000까지 들어온다.

브루트 포스로는 택도 없는 가지수를 구하게 될 수 있다는 것이다.

그리고 애초에 브루트 포스가 영문이름을 그대로 읽은 거라 좀 있어보이는거지 브루트 포스 자체는 완전 탐색으로 다른 알고리즘과 같이 사용하는게 아니면 효율적인 방법이라고 하기는 힘들다.

그래서 어떤 방법을 사용할 거냐면, 동적계획법을 사용할 것이다.

 

프로그램 동작

---

동적계획법이라고는 했지만, 여기서의 동작은 굉장히 단순하다.

동적계획법이란 분할 정복과 비슷한데, 분할 정복과는 다른 점은 작은 문제의 반복이다.

그리고 작은 문제의 해답을 적어놓는 메모이제이션도 있다.

우리는 이번 동적 계획법에서 어떤 문제를 반복하고 적어놓을 거냐면,

현재 자기 색과는 다른 두 색 중 더 작은 값 찾기를 반복하고 그 작은 값의 합을 적을 것이다.

이걸로 문제는 해결된다.

 

생각해보면 그리디 알고리즘과 비슷하다.

우리가 원하는 값은 최솟값인데, 작은 문제에서 계속해서 최솟값을 찾아 나아가기 때문이다.

하지만 그리디 알고리즘의 결과가 항상 최적의 값이 아니기도 하고, 이 문제에서의 경우 처음 시작값에 따라 결과가 달라져서 처음 시작값 세가지에 대한 그리디 탐색을 할 것이다.

 

1. 먼저 행이 3개인 2차원 dp 배열을 만들어준다.▼

 

 

앞의 R, G, B는 어떤 색을 더할건 지를 나타낸다.

그러므로 맨 첫번째 집의 R, G, B 값을 더해준다.▼

 

 

2. 그 다음부터는 내가 더했던 색이 아닌 다른 색들의 dp값을 가져와서 더해준다.

내가 직전에 더했던 색과 같은 색을 다시 더할 수 없기 때문이다.

다시 한 번 더 언급하는 거지만, 저기 앞에 써있는 R, G, B의 의미는 전 값에다가 R을, G를, B를 더했다는 의미이다.

일단은 R값부터 보면, R값은 자기 직전의 값과는 더할 수 없다.

하지만 G와 B값중 선택해서 더할 수는 있다.

우리는 이 중 작은 값을 선택해서 더하면 된다.▼

 

 

G값과 B값도 똑같이 해주면 된다.▼

 

 

3. 2번 과정을 마지막 집까지 반복해주면 된다.▼

 

 

4. 다 반복했으면 마지막 인덱스의 세 값중 가장 작은 값을 출력해주면 된다.▼

 

 

Swift 코드

---

let N = Int(readLine()!)!
var RGB = Array(repeating: Array(repeating: 0, count: 3), count: N)
var d = Array(repeating: Array(repeating: 0, count: 3), count: N)

for i in 0..<N {
    let h = readLine()!.split(separator: " ").map { Int(String($0))! }
    RGB[i][0] = h[0]; RGB[i][1] = h[1]; RGB[i][2] = h[2]
}

d[0][0] = RGB[0][0]
d[0][1] = RGB[0][1]
d[0][2] = RGB[0][2]

for i in 1..<N {
    d[i][0] = min(d[i - 1][1], d[i - 1][2]) + RGB[i][0]
    d[i][1] = min(d[i - 1][0], d[i - 1][2]) + RGB[i][1]
    d[i][2] = min(d[i - 1][0], d[i - 1][1]) + RGB[i][2]
}

print(min(min(d[N - 1][0], d[N - 1][1]), d[N - 1][2]))