백준 1149 - RGB거리

🔐 백준 1149 - RGB거리

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

🔑 풀이

시간 제한이 0.5초로 비교적 짧은 문제임을 유의해야 한다.

최대 집의 수는 1000이며, 각 집을 빨강, 초록, 파랑 중 하나로 칠할 수 있다. 따라서

집을 칠하는 조건을 차치하면, 경우의 가짓수는 최대 $ 3^N $ 일 것이다. 하지만 조건이

주어져 있으며, 이 조건을 만족하면서 집을 칠하는 경우는 DP 알고리즘으로 해결할 수 있다.

집 i를 빨강, 초록, 파랑으로 칠하는 비용을 cost[i][0], cost[i][1], cost[i][2]라 하고,

최소 비용 테이블을 다음과 같이 정한다.

• dp[i][0] : i번 집을 빨강으로 칠했을 때의 최소 비용
• dp[i][1] : i번 집을 초록으로 칠했을 때의 최소 비용
• dp[i][2] : i번 집을 파랑으로 칠했을 때의 최소 비용

그러면 이제 점화식을 다음과 같이 구성할 수 있다.

• dp[i][0] = min(dp[i−1][1], dp[i−1][2]) + cost[i][0]
• dp[i][1] = min(dp[i−1][0], dp[i−1][2]) + cost[i][1]
• dp[i][2] = min(dp[i−1][0], dp[i−1][1]) + cost[i][2]

🧩 코드