BOJ 1149 - RGB 거리

문제

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

전형적 DP 문제이지만 내가 너무 초보라 처음 풀었을때 엄청 헤맸다. 모든 집을 R,G,B 색 중 하나로 칠하는데 각 집들을 도색하는데 이웃과 색상이 같으면 안되는 조건 하에 도색 할수 있는 최소 비용을 구하는 문제이다.

풀이

각 집을 도색할때 이전 집과 색상이 같지않게 처리하면 모든 이웃이 색상이 같이 않게 되기 때문에 내가 R일때는 이전 집의 G or B의 비용 중 최소값, 내가 G일때는 R or B 중 최소값, 내가 B일때는 R or G 중의 최소값에 현재 집을 칠할 색의 비용을 계속 더해가주면 된다.

$ Cost[i][j] = min( Cost[i-1][(j+1)\%3], Cost[i-1][(j+2)\%3] ) + Home[j] $

Cost[i][j] = i번째집을 j색상으로 칠하려할때 i번째 집까지 도색할때 드는 최소 비용

Home[j] = 현재 집을 j색상으로 칠하려 할때 드는 비용

#include <stdio.h>

int cache[1001][3];

int min(int x, int y){ return (x>y)?y:x; }

int main(void) {
	int i,j,t,r[3];
	scanf("%d",&t);
	for(i=1;i<=t;i++){
		scanf("%d%d%d",&r[0],&r[1],&r[2]);
		for(j=0;j<3;j++)
			cache[i][j] = min(cache[i-1][(j+1)%3],cache[i-1][(j+2)%3])+r[j];
	}
	printf("%d",min(min(cache[t][0],cache[t][1]),cache[t][2]));
	return 0;
}

주의

% 연산자보다 + 연산자의 우선순위가 낮기 때문에 j + 2 % 3의 결과가 j + (2 % 3)가 되므로 직접 괄호로 (j + 2) % 3 이렇게 우선순위를 정해주어야 한다.