BOJ 1149 - RGB거리

문제 링크

문제#

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

출력#

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

풀이#

dp[i][color]를 i번째 집까지 칠했을 때, i번째 집 색이 color일 때의 최소 비용으로 두면 점화식이 바로 나온다. 예를 들어 빨강으로 칠하는 경우는 이전 집이 초록이나 파랑이었던 경우 중 더 작은 값에 현재 빨강 비용을 더하면 된다.

코드는 세 색에 대해 이 전이를 한 줄씩 채워 나간다. 마지막 집까지 계산한 뒤 dp[N][R], dp[N][G], dp[N][B] 중 최솟값을 고르면 전체 최소 비용이 된다.

코드#

#include <iostream>
#include <algorithm>
using namespace std;
 
const int MAX = 1001;
int dp[MAX][3];
 
void solve() {
 
	int n;
	cin >> n;
 
	for (int i = 1; i <= n; i++) 
		cin >> dp[i][0] >> dp[i][1] >> dp[i][2];
	
	for (int i = 2; i <= n; i++) {
		dp[i][0] += min(dp[i - 1][1], dp[i - 1][2]);
		dp[i][1] += min(dp[i - 1][0], dp[i - 1][2]);
		dp[i][2] += min(dp[i - 1][1], dp[i - 1][0]);
	}
 
	int ans = min(min(dp[n][0], dp[n][1]), dp[n][2]);
	cout << ans << '\n';
	
}	
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도#

• 시간 복잡도: 각 집의 세 색상 상태를 한 번씩 갱신하므로 $O(N)$이다.
• 공간 복잡도: DP 배열을 저장하므로 $O(N)$이다.

마무리#

dp[i][color]를 i번째 집까지 칠했을 때, i번째 집 색이 color일 때의 최소 비용으로 두면 점화식이 바로 나온다.