BOJ 1149 - RGB 거리

pa324·2019년 11월 6일
0

문제

풀이

첫번째 집에서 최소비용이 드는 색을 선택한다. 그러면 두번째 집에서는 첫번째 집이 사용한 색을 제외한 것 중 최소비용이 드는 색을 선택하는 방식으로, 전체 집을 칠하는 최소 비용을 구할 수 있다.

K = 0(빨강),1(초록),2(파랑)이라고 가정하면 아래와 같은 형태로 표현된다.

전체 집을 칠할때 드는 최소 비용을 구해야 하므로 점화식은 "i번째 집까지 j색을 칠할때 드는 최소 비용" 이라고 정의할 수 있다.

dp[i][j] = 집 i를 j색으로 칠했을때 까지의 최소비용이라고 정의

풀이

profile
안녕하세요

0개의 댓글