[BOJ] 백준 1149 RGB거리 (Swift)

문제

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

1149번: RGB거리

풀이

이 문제의 규칙을 쉽게 설명하면 같은 색으로 연속되게 집을 색칠하지 않고 집을 모두 칠하는 비용의 최소 값을 구해라! 입니다.
1번 집을 빨강으로 칠했다면, 2번 집은 초록과 파랑중에서 골라서 칠해주어야 합니다.

저는 다이나믹 프로그래밍을 떠올렸습니다.

3 * n 크기의 2차원 배열을 사용하였습니다.

초기 값은 처음 집을 칠하는 것이므로, 각각의 칠한 비용으로 설정하였습니다.

2번 집을 빨강색으로 칠하는 비용은,
1번 집은 파란색과 초록색으로 칠한 경우에서 더 적은 비용이 든 색깔을 골라주고, 2번 집을 빨강색으로 칠하는 비용과 더해주면 되겠죠?

마찬가지로 다른 색깔을 칠하는 비용도 그러할 것입니다.

따라서 점화식을 다음과 같이 구할 수 있습니다.

정의 : $color$ = 색깔별로 칠하는 비용, $f(n, color)$ = $n$번째 집을 color로 칠했을 때의 비용의 최소값
구하는 답: $min(f(n,0),f(n,1),f(n,2))$
초기값 : $f(0,n) = color(0, n)$
점화식: $f(n,i) = $
$if\ \ i == 0 \ \ \ min(f(n-1,1),f(n-1,2))$
$elif\ \ i == 1 \ \ \ min(f(n-1,0),f(n-1,2))$
$elif\ \ i == 2 \ \ \ min(f(n-1,0),f(n-1,1))$
$ + \ \ color(n,i)$

소스코드

후기

문제를 잘 읽어보고 이전의 결과로 다음 결과를 도출해낼 수 있어서 DP를 떠올렸습니다.