RGB거리

조건

1. 집을 빨강, 초록, 파랑중에 하나로 칠한다.
2. 이웃된 집은 같은 색으로 칠할 수 없다.

결과

• 모든 집에 색을 칠할 때 드는 최소 비용

해결 방법

• n번째 집이 빨강일 때, 초록일 때, 파랑일 때 드는 최소 값을 구한다.

1. dpn, r = min(dpn-1, g, dpn-1, b) + pricen, r
2. dpn, g = min(dpn-1, r, dpn-1, b) + pricen, g
3. dpn, b = min(dpn-1, g, dpn-1, r) + pricen, b

핵심 코드

for(int i = 0; i < house_num; i++) {
    if(i == 0) {
        result[i][0] = price[i][0];
        result[i][1] = price[i][1];
        result[i][2] = price[i][2];             
    }else {
        result[i][0] = Math.min(result[i-1][1], result[i-1][2]) + price[i][0];
        result[i][1] = Math.min(result[i-1][0], result[i-1][2]) + price[i][1];
        result[i][2] = Math.min(result[i-1][1], result[i-1][0]) + price[i][2];
    }
}
System.out.println(Math.min(result[house_num-1][0], Math.min(result[house_num-1][1], result[house_num-1][2])));

전체 소스 코드는 여기서 확인하실 수 있습니다.