[백준 / BOJ] 1149 RGB거리

문제

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

1149번: RGB거리

 

집의수 N이 주어진다. 이때, 각 집은 빨강,초록,파랑으로 칠할수있고, 색깔은 연속되게 칠하지못한다.

각 색깔로 칠하기위해 드는 비용이 주어졌을때 최솟값을 구하는 문제다.

 

풀이

N이 최대 1000이고, 시간제한이 0.5라서 완탐으로 풀경우 시간초과가 난다.

 

Dp를 이용하면 풀리는 문제였다.

 

각 색깔을 연속으로 칠할수없다는 조건이있다.

즉, 현재 색 R, G, B를 칠하기 위해선, 다음 조건이 성립해야한다.

 

R : 전 위치의 집색 -> G , B

G : 전 위치의 집 색 -> R , B

B : 전 위치의 집 색 -> R , G

 

dp를 이차원으로

(dp[칠할집의 숫자][색] = 비용)

만들고 전단계에서 현재 색에맞는 최솟값을 가져오면된다. 예를들어, 현재 칠할 집의 숫자가 5이고, 빨강색(R : 0, G : 1, B : 2 일때)을 칠할려한다면,

dp[5][0] = min(dp[4][1], dp[4][2]) + 빨간색을 칠하는 비용

과 같은 식이 나온다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1149%20RGB%EA%B1%B0%EB%A6%AC/main.cpp

devxb/JJUNalgo