[C/C++ 백준 1149번] RGB거리 (Silver 1)

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

1149번: RGB거리

다이나믹 프로그래밍이라는 카테고리 안에서는 매우 비슷한데, 단지 차원이 하나 더 늘어난 이차원 배열이라는 것만 다른 문제인것 같다. 마찬가지로 이차원 배열 dp[1001][3]을 선언한뒤, dp[i][j]를 해당 집을 그 색으로 색칠했을 때까지의 최소 비용이라고 한다. 

26	40	83
49	60	57
13	89	99

 

26	40	83
89	86	83
96	172	182

 

위의 테이블이 사이트에 나온 예제이고, 그 밑이 그에 따른 dp 테이블이다. 각 i행의 dp를 정할때, i-1행의 dp중 최소값과 해당 행의 hc(housecolor)를 더해 정한다. 코드는 다음과 같다.

---

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	int N;
	scanf("%d", &N);
	int hc[1001][4]={};
	for(int i=1; i<=N; i++){
		for(int j=1; j<=3; j++){
			scanf("%d",&hc[i][j]);
			int mini=987654321;
			for(int k=1; k<=3; k++){
				if(k==j)
					continue;	
				mini=min(mini, hc[i-1][k]);
			}
			hc[i][j]=hc[i][j]+mini;
		}
	}
	int mini2=987654321;
	for(int q=1; q<=3; q++)
		mini2=min(hc[N][q], mini2);
	printf("%d",mini2);
}

---