편집 시간: 2022년 2월 16일 오후 4:10
코드
Algorithm/1149.py at main · Junroot/Algorithm
풀이
모든 경우의 수를 다 구해보는 방법 밖에 없다. 함수 f(index, last_color)를 만들어 함수를 아래와 같이 정의한다.
- f(index, last_color): index번째 집이 last_color를 사용하지 못할 때 최소 index부터 n번째 집까지 칠하는데 최소 비용
그러면 아래와 같은 점화식이 만들어진다.
f(index, last_color) = min( (index번째 집의 color1 비용) + f(index + 1, color1), (index번째 집의 color2 비용) + f(index + 1, color2) )
color1과 color2는 last_color가 아닌 나머지 색깔들이다. 이 때 중복된 연산을 피하기 위해서 DP를 함께 사용하면 시간초과를 피할 수 있다.